Lecture 8: Complexity; log, linear, quadratic, exponential algorithm

本课通过大量例子展示了不同的算法复杂度，包括对数级，线性级，二次方级和指数级。本课所讲的算法复杂度并未涉及高深的数学知识，因此并不需要强大的数学基础。不同于本课程，MIT的“算法导论”课程需要非常强大的数学理论基础。

此笔记详尽包括了本课展示的四个例子七个程序段。那么下面就开始第一个例子。

例1：仅用加减乘数四则运算来计算a的b次方，即a**b

第一个方法用了普通while循环，非常简单，程序段1.1如下：

def exp1(a, b):

    ans = 1

    while b > 0:

        ans *= a

        b -= 1

    return ans

在这个函数的while循环中，一共做了3b次操作，加上while循环之外的操作，总操作数可表达为 T(b) = 3b + 2        (1)

第二个方法用了递归算法，思路也非常简单，如下：

• a**b = a*(a**(b-1))


• a**1 = a    (base-case)

那么这个程序就可以这样实现，程序段1.2如下：

def exp2(a, b):

    if b == 1:

        return a

    else:

        return a * exp2(a, b-1)

在这个递归函数中，我们其实运用了这样一个递归式：T(b) = 3 + T(b-1)，如果我们把T(b-1)也表达成同样的形式，即T(b-1) = 3 + T(b-2)，那么我们可以得出：T(b) = 3k + T(b-k)。由此可得，当b-k = 1时，总操作数T(b) = 3b - 2        (2)

将(1)与(2)比较，我们发现函数exp2比函数exp1少做了4次操作。这个差别并不是特别显著，说明性能改进也不是特别明显。那么我们就有了更优化的程序，程序段1.3如下：

def exp3(a, b):

    if b == 1:

        return a

    if b % 2 == 0 and b != 0:

        return exp3(a*a, b/2)

    else:

        return a * exp3(a, b-1)

在这个函数exp3中，考虑了指数b的奇偶性，简要思路如下：

• 当b为偶数时：a**b = (a*a)**(b/2)


• 当b为奇数时：a**b = a*(a**(b-1))

那么根据这个思路，我们可以写出如下递归式：

• 当b为偶数时：T(b) = 6 + T(b/2)


• 当b为奇数时：T(b) = 6 + T(b-1)


• 总体来说：T(b) = 12 + T((b-1)/2)

那么，我们可以简化成 T(b) = 12 + T(b/2) = 12k + T(b/(2**k))，所以当2**k = b时， k = log2(b)。由此可得，T(b) = 12log2(b) + 1        (3)

将(1),(2)和(3)进行比较，通过分析T(b)的函数图像，我们会发现：当b足够大时，log2(b)的增长率比3b的增长率小很多。

这种增长率(Rate of growth as input size grows)可以用渐近记号(Asymptotic notation)来表示。这里常用的是Big O Notation，即O()。它表示函数的上界，即当输入值足够大的时候，这个函数的增长值不会超过上界(upper limit to the growth of function as input get large)。

简单举个例子：f(x) = O(n) 的意思就是 当x足够大的时候，0<= f(x) <= cn，其中c为常数。

这是一个渐进分析的表示方法，具体定义可以参考《算法导论》。

那么了解了O记号之后，我们就可以将程序段(1),(2),(3)的算法复杂度表示出来了：

• (1) = O(n)


• (2) = O(n)


• (3) = O(log n)

由此可得，程序段(3)的算法复杂度远远低于前面两种算法。

那么在见到了线性级算法（O(n)）和对数级算法（O(logn)）之后，下面两个例子则是二次方级算法和指数级算法。

例2：这是一个只用加法计算a*b的算法，复杂度为O(n^2)

def g(a, b):

    x = 0

    for i in range(a):

         for j in range(b):

             x += 1

    return x

例3：这是一个解汉诺塔游戏的算法，复杂度为O(2^n)。（根据百度百科，汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。）

def Towers(size, fromStack, toStack, spareStack):

    if size == 1:

        print "move disk from ", fromStack, " to ", toStack

    else:

        Tower(size - 1, fromStack, spareStack, toStack)

        Tower(1, fromStack, toStack, spareStack)

        Tower(size - 1, spareStack, toStack, fromStack)

具体证明过程就不累述了，可以参考百度百科里面汉诺塔的递归算法。

现在，我们来比较一下不同算法的运算速度：

假设输入值大小为n = 1000位

• 对数级(Logarithm)要花10纳秒(nanosecs)


• 线性级(Linear)要花1微秒(microsecs)


• 二次方级(Quadratic)要花1厘秒(millisecs)


• 指数级(Exponential)要花10^284年！

更直观地比较前三个：

• 对数级花10厘秒


• 线性级花1秒


• 二次方级要花16分钟

因此，我们可以通过算法复杂度看出算法的性能和运算效率。可以说，在输入数据很大时，要尽可能避免指数级算法。而对数级算法在输入数据很大情况下，可以大大提高运算效率，因此在设计算法时要尽可能向这里靠拢。

本课后半部分介绍了搜索(search)的算法。这里主要举了普通搜索和二分搜索两个例子。

例1：普通搜索，复杂度为O(n)

def search(s, e):

    answer = None

    i = 0

    numCompare = 0

    while i < len(s)  and answer == None:

        numCompare += 1

        if e == s[i]:

             answer = True

        elif e < s[i]:

             answer = False

        i += 1

    return answer

例2：二分搜索，复杂度为O(logn)

def bsearch(s, e, first, last):

    if last - first < 2:

        return s[first] == e or s[last] == e

    mid = first + (last - first) / 2

    if s[mid] == e:

        return True

    if s[mid] > e:

        return bsearch(s, e, first, mid - 1)

    return bsearch(s, e, mid + 1, last)

总结：本课介绍了算法复杂度的基本概念，非常重要，初学者本课必看！