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) 总结：本课介绍了算法复杂度的基本概念，非常重要，初学者本课必看！

Lecture 9: Binary search, bubble and selection sorts 本课前半部分重温了上节课略过的二分法搜索，后半部分开始讲排序问题，并举了两个最经典但是最没有效率的两种排序，冒泡排序和选择排序。 鉴于上节课最后已经提到过了二分法搜索，那么这里就不再累述具体细节，标程也可以从上节课的笔记中找到。但是这里必须要提到的，是二分法的通用模板(Template/generalizing binary search)，这个模板是一个简单的分治法(Divide and conquer method)，在下节课会讲到。那么，二分法的模板如下：找到数据的中点检查是否是符合要求的答案如果不是，那么就将问题规模缩小，重复相同的操作（注意：运用此模板可以讲问题规模以常数倍逐次缩小，从而大大提高运算效率） 本课后半节讲到了排序，并举了排序中最经典，最简单，但也是效率最低的两种排序——选择排序和冒泡排序。可以说，这两种排序的思路有类似之处，复杂度都为二次方级，即O(n^2)。那么下面我就会给出这两种排序的标程，当然初学者也可以自己尝试：例1：选择排序def selectSort(L):    for i in range(len(L)-1):         minIndex = i         minVal = L[i]         j = i + 1         while j < len(L):              if minVal > L[j]:              minIndex = j              minVal = L[j]              j = j + 1         temp = L[i]         L[i] = L[minIndex]         L[minIndex] = temp    return L选择排序的算法思想是这样的：取minIndex表示最小值的元素号码，取minVal表示最小值的值。每次循环中找出最小值存入minVal，其元素号码存入minIndex，然后交换数据。第一次循环找出最小的数，第二次找出第二小的数，依此类推。 例2.1：冒泡排序def bubbleSort1(L):     l = len(L) - 2     i = 0     while i < l:           j = l           while j >= i:                  if L[j + 1] < L[j]:                  L[j], L[j + 1] = L[j + 1], L[j]                  j -= 1           i += 1     return L冒泡排序的算法思想是这样的：每次从最后开始往前滚，邻接元素两两相比，小元素交换到前面。第一轮循环把最小的元素上浮至第一位置，第二小的元素上浮至第二位置，依此类推。 例2.2：冒泡排序（优化）def bubbleSort2(L):     sort = True     while sort:            sort = False            for i in range(len(L) - 1):                    if L[i] > L[i + 1]:                            L[i + 1], L[i] = L[i], L[i + 1]                            sort = True     return L这里优化之处在于：当for循环中没有交换时，列表则被视为已经排好，则不再进行多余的操作。 在本课中还需要提到的一个知识点是循环不变量(Loop Invariant)，这表示在循环结构中每次循环都为真的属性。在这些排序中，循环不变量是这样的：列表被分为两部分：前半部分已经被排好，后半部分则是未排好的每次循环被排好的部分不变，但是规模+1，直到后半部分什么都不存在，而整个列表都被排好（注意：对于循环不变量的具体证明，各位可以参考《算法导论》第二章算法入门，有详细解释） 总结：这里介绍的两种排序都不常用，因为效率太低，但是对于初学者来说，这是排序入门的两个例子。

Lecture 12: More about debugging, knapsack problem, introduction to dynamic programming 本课主要分为三个部分，第一部分介绍了更多在调试时候的注意点；第二部分例举了多个经典优化问题；而第三部分则简要介绍了动态规划。 第一部分提出了许多在调试时应该注意的地方，下面大概有三个重要点，将逐个讲明。第一个要点是在调试的时候，各位可以注意程序是否出现了以下错误（有些可能非常简单，但仍需要小心谨慎）：自变量顺序错误(Reversed order of arguments)；拼写问题(Spell mistakes)；忘记初始化(Initialization)，注意在使用循环时，初始化应该在循环内部还是外部；对象与值对等(Objects vs. value equality)；注意别名混淆(Aliasing)，例如列表的深复制和浅复制；副作用(Side-effects)，注意程序是否会产生不需要的操作而影响结果。第二个要点，是在平时写程序并调试的时候，要注意养成时时记录自己错误的习惯，总结成一个个人犯错模型(Personal model of mistakes)。那么在调试的时候，就可以首先查找是否又出现了以前犯过的错误。第三个要点是在调试的时候，要记录下已经尝试过的修改。不是所有修改都会一次成功，而且有时候调试和修改会花很长时候。因此，这些记录就可以避免重复进行同样的无效修改。另外，由于修改可能会导致程序变得更加糟糕，确保程序可以回转则非常重要。因此，要保存原本的未修改程序和每个修改过的版本（可命名为V1.0, V1.1, V2.1等等） 第二部分则提出了新的问题类型，即最优化问题(Optimization problem)。这些问题都有以下两个显著的特点：包括取最大值或最小值的函数必须满足一定的约束条件最优化问题包括以下五个非常经典的子类型：最短路径问题(Shortest Path Problem)旅行商人问题(Travelling Saleperson Problem)装箱问题(Bin Packing Problem)调整问题(Sequence Alignment Problem)背包问题(Knapsack Problem)大多数新的优化问题可以简化为以上五个子类型，而运用这些已知问题的解法可以解决新的问题。 本课重点讲述的是第五种题型，即背包问题。背包问题又分为两种类型，一是连续背包问题，二是0/1背包问题。背包问题类型1：连续背包问题例：假设一个贼闯入一户人家，他有一个背包可以装10kg的东西。屋里有以下值钱的东西：4kg金沙3kg银沙10kg葡萄干那么我们就来系统化一下这类问题：① 创建一个函数，要求这个函数的最大值或最小值。在这个例子中，就是求背包里面装的东西的最大价值。我们就可以由函数：f = 金沙的价值 x 金沙的重量 + 银沙的价值 x 银沙的重量 + 葡萄干的价值 + 葡萄干的重量。求这个函数f的最大值。② 考虑约束条件。在这个例子中，金沙，银沙和葡萄干的重量总和 <= 10kg这个问题的解法非常简单：我们先取4kg金沙，3kg银沙，再取3kg葡萄干。这就是一个简单的贪心算法(Greedy algorithm)，即每一步都是最优解的算法。然而局部最优策略并不代表全局最优策略，我们可以另一种背包问题，即0/1背包问题。 背包问题类型2:0/1背包问题（基本上这是不连续背包问题）例：假设这个小偷的背包仍然只能装10kg的东西，但是他闯入的屋主家只有如下物品：一个手表（重1kg，价值10）一个收音机（重3kg，价值5）一个花瓶（重5kg，价值7）一幅油画（重8kg，价值9）我们也来系统化这个问题：① 我们有n件物品，但每一次只能选择拿整件物品或者不拿这件物品；② 每个物品都有重量和价值，我们要找到最优解，即最大值。那么，我们会有如下两种方法去解决这个问题：贪心算法(Greedy algorithm)穷举法(Brute-force algorithm)贪心算法前面已经提到过了，在每一步都取最优解，即取价值最高的物品。所以就是拿一个手表，再拿一幅油画，所以总价值为10 + 9 = 19。这样的算法即快速又简单，但并不是最优解。最优解是什么？其实就是一个手表，一个收音机加一个花瓶，总价值为10 + 5 + 7 = 22。这个用穷举法也可以做，但是非常慢，在这里一共有2^4 = 16种可能性。但当输入值n很大的时候，就有2^n种可能性，当n足够大的时候，比如n=50，穷举法就需要花很长很长的时候去算出最优解。那么，这时我们为了提高算法效率，就可以运用动态规划。 什么是动态规划？这就是第三部分讲的内容。由于动态规划是下一节课的内容重点，我就会在下一个笔记中详细讲述，并且写出0/1背包问题的两种解法。 总结：介绍最优化问题系列，重点讲述背包问题，非常重要，初学者必看！

Lecture 13: Dynamic programming: overlapping subproblems, optimal substrcture 本课重点讲述了动态规划，介绍了其核心思想，即默记法。本课前半部分用斐波纳契数的例子详细介绍默记法的使用方法。后半部分介绍了决策树和用它解决0/1背包问题的两个程序样例。 动态规划(Dynamic programming)，根据百度百科所述，是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在20世纪50年代初，美国数学家R.E.Bellman（贝尔曼）等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划最关键的地方在于，存在一种子问题和最理想子结构重叠的情况。这个说法非常抽象，但简单来说就是如果子问题的最优解被重复使用的话，我们就可以使用动态规划。下面就举一个例子来详细解释：在Lecture 4的时候，有一个例子斐波那契数Fibonacci numbers，当时有如下程序：def Fib(n):    if n == 1 or n == 0:        return 1    else:        return Fib(n - 1) + Fib(n - 2)那么，如果要计算Fib(5)的结果，我们会用到Fib(4)和Fib(3)的结果，而Fib(4)又用到了Fib(3)和Fib(2)的结果，依此类推。我们会发现，Fib(3)，Fib(2)的结果被多次调用，而我们又需要花时间去计算Fib(3)和Fib(2)，那么这就造成了累赘计算。相信到这里，大家都会这样觉得，为什么不把这些结果存下来，这样以后用到的时候就可以直接使用了呢？没错，这就是我们所说的默记法。 默记法(Memorization)是动态规划的核心内容。具体方法如下：我们在第一次计算的时候就记录一个值然后再后续的问题中使用这个值这个概念非常简单，容易理解。那么对于上面的斐波那契的例子，我们就可以运用默记法，标程如下：def FastFib(n, memo):    if not n in memo:        memo[n] = FastFib(n - 1, memo) + FastFib(n - 2, memo)    return memo[n] def FastFibonacci(n):    memo = {0:1, 1:1} # initialize the memo    return FastFib(n, memo) 本课的后半部分则讲了0/1背包问题的两个解法，下面例1是普通解法，只是用了简单的决策树，而例2则用了动态规划，优化了例1。两个例子如下：例1：普通解法def maxVal(w, v, i, aW):    if i == 0:    if w[i] <= aW:        return v[i]    else:        return 0    without_i = maxVal(w, v, i-1, aW)    if w[i] > aW:        return without_i    else:        with_i = v[i] + maxVal(w, v, i-1, aW - w[i])    return max(with_i, without_i) 例2：动态规划def fastMaxVal(w, v, i, aW, m):    try:        return m[(i, aW)] # to check whether the thing is in the memo or not    except KeyError:        if i == 0:        if w[i] <= aW:            m[(i, aW)] = v[i]            return v[i]        else:            m[(i, aW)] = 0            return 0        without_i = fastMaxVal(w, v, i-1, aW, m)        if w[i] > aW:            m[(i, aW)] = without_i            return without_i        else:            with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)        res = max(with_i, without_i)        m[(i, aW)] = res        return res def MaxVal0(w, v, i, aW):    m = {}    return fastMaxVal(w, v, i, aW, m)这个程序的算法复杂度为O(ns)，n为可选择物品的总数量，s为背包可以装的物品数量。这个算法不仅需要O(ns)的时间，也需要O(ns)的空间。可以说，这也是一个用空间换时间的算法。 那么我们再来从复杂度的方面考虑动态规划。根据百度资料，能用动态规划解决的问题，肯定能用搜索解决。但是搜素时间复杂度太高了，怎么优化呢？我们就想到了记忆化搜索，也就是默记法，就是搜完某个解之后把它保存起来，下一次搜到这个地方的时候，调用上一次的搜索出来的结果。这样就解决了处理重复状态的问题。动态规划之所以速度快是因为解决了重复处理某个状态的问题。记忆化搜索是动态规划的一种实现方法。搜索到i状态，首先确定要解决i首先要解决什么状态。那么那些状态必然可以转移给i状态。于是我们就确定了状态转移方程。然后我们需要确定边界条件。将边界条件赋予初值。此时就可以从前往后枚举状态进行状态转移拉。（以上三段均来自于百度：http://zhidao.baidu.com/question/407709820.html） 总结：详细介绍了动态规划和其核心内容默记法，非常有用，初学者必看！