Python数据结构与算法--算法分析

在计算机科学中，算法分析（Analysis of algorithm）是分析执行一个给定算法需要消耗的计算资源数量(例如计算时间，存储器使用等)的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度，值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。算法分析是计算复杂度理论的重要组成部分。

本文地址：http://www.cnblogs.com/archimedes/p/python-datastruct-algorithm-analysis.html，转载请注明源地址。

一个有趣的问题经常出现，那就是两个看似不同的程序，到底哪个更好呢?

要回答这个问题, 我们必须知道程序和代表程序的算法有很大的区别. 算法是一个通用的, 解决问题的一条条的指令. 提供一个解决任何具有指定输入的实例问题方法, 算法产生期望的结果. 一个程序, 另一方面, 是将算法用某一门编程语言代码实现. 有很多的程序实现的同一算法, 取决于程序员和编程语言的使用.

进一步的探究这种差异, 考察下面的函数代码. 这个函数解决一个简单的问题, 计算前n个自然数的和. 解决方案遍历这 n 个整数, 相加后赋值到累加器.

def sumOfN(n):
   theSum = 0
   for i in range(1,n+1):
       theSum = theSum + i
   return theSum

print(sumOfN(10))

接下来看下面的代码. 第一眼看上去感觉很奇怪, 但是深入理解之后你将发现这个函数和上面的函数完成同样的工作. T原因是这个函数不是那么明显，代码难看. 我们没有使用好的变量名导致可读性很差, 并且还声明了没有必要声明的变量.

def foo(tom):
    fred = 0
    for bill in range(1,tom+1):
       barney = bill
       fred = fred + barney
    return fred
print(foo(10))

到底哪段代码更好呢.问题的答案取决于你的标准.如果你只关注可读性，函数sumOfN 肯定比 foo 好. 事实上, 你可能在你的编程启蒙课上见到过很多教你编写可读性好和易于理解的程序的例子. 然而在这里, 我们还对算法感兴趣. 

作为替代空间的需求, 我们基于它们执行时间来分析和比较算法. 这种度量有时候被称为算法的“执行时间”或"运行时间". 我们测量 sumOfN 函数执行时间的一种方法是做个基准分析. 在Python, 我们可以通过一个函数针对我们所使用的系统上标记程序的起始和结束时刻. 在 time 模块有一个被称为 time 的函数，将返回系统的当前时间. 通过两次调用这个函数, 起始和结束, 然后计算差值, 我们可以得到准确的执行时间.

Listing 1

import time

def sumOfN2(n):
   start = time.time()

   theSum = 0
   for i in range(1,n+1):
      theSum = theSum + i

   end = time.time()

   return theSum,end-start

Listing 1 展示了sumOfN 函数在求和前后的时间开销. 测试结果如下:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds

我们发现时间相当的一致并且都平均花费 0.0019 秒执行程序. 那么假如我们将n增大到 100,000 会怎样呢?

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds
>>>

再次, 时间更长, 非常的一致, 平均10倍的时间. 将 n 增大到 1,000,000 我们达到:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds
>>>

在这种情况下, 平均执行时间又一次被证实是之前的10倍.

现在来看一下 Listing 2, 提出了一个不同的解决求和问题的方法. 这个函数, sumOfN3, 运用了一个等式：∑n_i = (n+1)n/2来计算前 n 个自然数取代循环计算.

Listing 2

def sumOfN3(n):
   return (n*(n+1))/2

print(sumOfN3(10))

如果我们针对 sumOfN3 做一些测试, 使用5种不同的n值(10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000), 我们得到下面的结果:

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

对于这个输出，有两个方面需要注意. 第一, 上面程序的运行时间比前面的任意一个的运行时间都短. 第二, 无论n为多大执行时间都是一致的. 

但是这个标准真正地告诉我们什么?直观地说, 我们可以看到，迭代的解决方案似乎是因为一些程序步骤被重复而做更多的工作. 这是它占用更多运行时间可能的原因. 当我们增加 n的时候循环方案执行时间也在增加. 然而,有一个问题. 如果我们跑相同的功能在不同的计算机或使用不同的编程语言,我们可能会得到不同的结果. 如果是老式计算机将可能在 sumOfN3上执行更多的时间.

我们需要一种更好的方式来描述这些算法的执行时间。基准的方法计算实际的执行时间。它并不真的为我们提供了一个有用的测量，因为它是依赖于特定的机器，当前时间，编译，和编程语言。相反，我们要有一个特性，是独立于程序或计算机的使用。这一方法将独立地判断使用的算法是有用的，可以用来在实现算法比较。

一个易位构词实例

一个展示算法不同的数量级的例子是经典的字符串易位问题. 一个字符串和另一个字符串如果仅仅是字母的位置发生改变我们就称为易位. 例如, ‘heart‘ 和 ‘earth‘ 就互为易位. 字符串‘python‘和 ‘typhon‘ 也是. 为简化问题的讨论,我们假设字符串中的字符为26个英文字母并且两个字符串的长度相同. 我们的目标是写一个boolean 类型的函数来判断两个给定的字符串是否互为易位.

方法1: 逐一检测

对于易位问题，我们的第一个解决方案是检测第一个字符串的每一个字母是否在第二个字符串中. 如果成功检测所有的字母, 那么两个字符串是易位的. 检查一个字母成功后将使用 Python的特殊值 None 取代. 然而, 因为在 Python 中string是不可变的, 第一步将字符串转换成 list. 看下面的代码：

def anagramSolution1(s1,s2):
    alist = list(s2)
    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1(‘abcd‘,‘dcba‘))

方法2: 排序比较

另一个解决方案基于的思想是：即使两个字符串 s1 和 s2 不同, t它们易位当且仅当它们包含完全相同的字母集合. 因此, 如果我们首先将两个字符串的字符按照字典排序, 如果两个字符串易位，那么我们将得到完全一样的两个字符串. 在 Python 我们可以使用list的内建方法 sort 来简单的实现排序.看下面的代码：

def anagramSolution2(s1,s2):
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if alist1[pos]==alist2[pos]:
            pos = pos + 1
        else:
            matches = False

    return matches

print(anagramSolution2(‘abcde‘,‘edcba‘))

第一眼看上去，你可能认为程序的时间复杂度为O(n), 因为只有一个简单的比较n个字母的循环. 然而, 两次调用 Python sort 函数都没有考虑开销. 以后我们会介绍, 排序将花费的时间复杂度为 O(n²) 或 O(nlogn), 于是排序相比循环占主导地位.

方法3: 暴力

一个 brute force 计数方法是枚举出所有的可能性. 对于这个问题, 我们可以使用 s1 的字母简单地生成所有的可能字符串并看 s2 是否出现. 然而,这种方法有一个难点. 我们列举出s1的所有可能性,第一个字母有 n 种可能,第二个位置有n-1种可能, 第三个位置有n-2种可能,……. 总共的可能性为：n*(n-1)*(n-1)*3*2*1 = n!.已经证明 n!递增非常快,当n非常大的时候, n! 递增速度超过 2ⁿ .

方法4: 计算和比较

最后一个解决方案是基于这样的一个事实：任意两个易位的字符串都有相同的‘a‘的数目,相同的‘b‘的数目,相同的‘c‘的数目……. 为了判断两个字符串是否易位,我们首先计算每一个字母的次数. 因为只有26个可能的字母, 我们可以使用一个list来保存26个计数, 每一个保存可能的字母. 每次当我们看到一个特别的字母，我们就增加对应的计数. 最后, 如果两个list的对应计数完全相同, 两个字符串就是易位的. 看下面的代码：

def anagramSolution4(s1,s2):
    c1 = [0]*26
    c2 = [0]*26

    for i in range(len(s1)):
        pos = ord(s1[i])-ord(‘a‘)
        c1[pos] = c1[pos] + 1

    for i in range(len(s2)):
        pos = ord(s2[i])-ord(‘a‘)
        c2[pos] = c2[pos] + 1

    j = 0
    stillOK = True
    while j<26 and stillOK:
        if c1[j]==c2[j]:
            j = j + 1
        else:
            stillOK = False

    return stillOK

print(anagramSolution4(‘apple‘,‘pleap‘))

依然, 这种解决方案包含大量的循环. 然而, 与第一种方案不同, 它们都没有被嵌入. 前两个循环方案都在n的基础上计算字母. 第三个方案的循环, 比较两个字符串中counts的数目, 只需要 26 步 因为一个字符串只有26种可能的字母. 累加在一起我们得到 T(n)=2n+26 步. 即是 O(n). 我们找到了这个问题的线性时间解法.

离开这个例子之前，我们需要说的是空间开销.虽然最后的解决方案能够在线性时间内运行，它能成功必须要通过使用额外的存储保持两个列表中的字符数。换句话说，该算法使用了空间换时间.

这是一种常见的情况. 在许多场合，你需要做出决定的时间和空间之间的权衡。在目前的情况下，额外空间量是不显著的。然而，如果下面的字母有数百万字，就必须更多的关注空间开销。作为一个计算机科学家，当在选定算法的时候，主要由你来决定如何利用计算机资源来解决一个特定的问题.

您还可能感兴趣：