感谢猫冬同学给予我这个再次学习算法的机会,本系列笔记主要以章节形式划分,内容以我认为的重难点及部分习题的探讨为主,希望能给各位带来启发,在此表示感谢!(更新较慢,但我希望我能坚持写完整本书的笔记整理,请见谅!)

引言

我学过数据结构的基础课,记得一开始老师就讲时间复杂度,还需要计算一些代码中的时间复杂度。当时没怎么搞清楚平均、最坏情况时间复杂度等,也就是会数一下循环,算一下阶,具体要计算平均时间复杂度是完全靠脑洞做的,阅读了这本书后才明确原来就是数学期望……

书中具体的例子我不会描述得特别详细,因为我最近也比较忙……请见谅,不过我会把我的想法加进来,不一定正确,但希望能给您一些小小的启发。

另外,比较有意思的一件事是我的数据结构的老师说过,所有的n^2的算法都可以优化为nlog n,我觉得可能和递归有关系,但是老师没有明确给出依据,如果您对这个问题有了解或者感兴趣,欢迎和我讨论,谢谢!

1.1_算法

  1. [P1-P2]参数(parameter)是一个问题中可能在其描述中包含的一些未指定取值的变量。因为问题中包含参数,所以它代表着一类问题,每对参数进行一次赋值,就得到其中一个问题。每次特定赋值就称为该问题的一个实例(instance)。
  2. [P4]当算法的名字看起来与其返回值很吻合时,我们就将算法写为函数(function)。否则,就将其写为过程(procedure,C++中的void函数),并使用引用参数(reference parameter,也就是按地址传递的参数)来返回值。如果参数不是数组,在声明它时,会在数据类型名的末尾添加一个&符号。它在这里的意思是:这个参数包含算法的一个返回值。因为数组在C++中是自动按引用传递的,而且在传递数组时,C++中也没有使用&符号,所以我们没有使用&来表示数组中包含算法的返回值。相反,由于C++中使用保留字const来防止对所传递数组进行修改,所以我们使用const表示数组中不包含算法的返回值。

1.2_开发高效算法的重要性

1.2.1_顺序查找与二分查找的对比

1.2.2_斐波那契序列

  1. [P9算法1.7]若使用迭代来计算斐波那契序列的第n项,则在计算一个值时,将其保存在一个数组中,后面再需要它时,就不用再重新计算了。
  2. [P10]算法1.7是动态规划方法(dynamic programming approach)的一个例子。

1.3_算法分析

1.3.1_复杂度分析

  1. [P11]注意“输入规模”不是“输入”。根据情况选择输入规模的合理度量。
  2. [P11]在确定了输入规模后,我们选择某条指令或某组指令,使算法完成的总工作量大体与这条指令或这组指令的执行次数成正比。我们将这条指令或这组指令称为算法的基本运算。
  3. [P11]基本运算的选择没有一成不变的规则,大多由个人判断力和经验决定。
  4. [P11]有时可能希望考虑两种不同的基本运算。例如,在通过比较键来完成排序的算法中,经常希望将比较指令和赋值指令分别看作基本运算。
  5. [P11]在某些情况下,基本运算的执行次数不仅取决于输入规模,还与输入值(比如顺序之于顺序查找)有关。
  6. [P11]T(n)称为算法的所有情况时间复杂度(every-case time complexity),对T(n)的计算称为所有情况时间复杂度分析。T(n)定义为:对于输入规模n的一个具体取值,该算法执行基本运算的次数。
  7. [P12]W(n)称为最差情况时间复杂度(worst-case time complexity)。W(n)定义为:当输入规模为n时,该算法执行其基本运算的最大次数。如果存在T(n),则W(n)=T(n)。
  8. [P12]A(n)称为算法的平均情况时间复杂度(average-case time complexity)。A(n)定义为:对于输入规模n,该算法执行基本运算的平均次数,也就是均值(期望)。为了计算A(n),需要为所有规模为n的不同输入指定相应概率。和W(n)一样,如果存在T(n),则A(n)=T(n)。
  9. [P13]只有当实际情景不会与“平均值”偏离太多时(也就是说标准偏差很小时),才能说这个平均值是“典型值”。
  10. [P13]B(n)成为算法的最佳情况时间复杂度(best-case time complexity)。B(n)的定义为对于输入规模n,该算法执行基本运算的最小次数。和W(n)、A(n)的情景一样,如果T(n)存在,则B(n)=T(n)。
  11. [P14]对于不存在T(n)的算法,我们执行W(n)和A(n)分析的频率远高于B(n)的分析。
  12. [P14]一般情况下,复杂度函数(complexity function)可以使任何一个将正整数映射为非负实数的函数。

1.3.2_理论应用

1.3.3_正确性分析

1.4_阶

1.4.1_阶的直观介绍

  1. [P16]与仅知道阶数相比,若准确地知道时间复杂度,则可掌握更多信息。比如对于特定的实例,阶数高的算法也可能效率高于阶数低的算法(函数图象交点)。

1.4.2_阶数的严谨介绍

  1. 关于大O、Ω、小o、Θ等,请参考微积分中的有关分析即可。证明只需严格对照定义。
  2. [P19]O(n^2)的复杂度函数并非一定要有二次项,只要它的曲线最终低于某个纯二次函数即可。
  3. [P20]例1.17是一个不错的反证法的例子。
  4. [P21定义]“大O”是指必然存在“某个”正实常数c,使此上限成立。而“小o”的定义说该上限必须对于“每个”正实常数c成立。
  5. [P21]定理1.2。[P22]例1.20,o(f(n))和O(f(n))-Ω(f(n))不一定是同一个集合。
  6. [P22]阶的性质:
    1. g(n)∈O(f(n)), 当且仅当f(n)∈Ω(g(n))
    2. g(n)∈Θ(f(n)), 当且仅当f(n)∈Θ(g(n))
    3. 若b>1, a>1, 则log_{a}n∈Θ(log_{b}n), 即所有对数时间复杂度都属于同意复杂度类别, 我们用Θ(lgn)代表这一类别
    4. 若b>a>0, 则a^n∈o(b^n), 即所有指数复杂度函数都不在同一复杂度类别中
    5. 对于所有a>0, 有a^n∈o(n!), 即n!比任何指数复杂度函数都要差
    6. 复杂度类别的顺序:
      Θ(lgn) Θ(n) Θ(nlgn) Θ(n^2) Θ(n^j) Θ(n^k) Θ(a^n) Θ(b^n) Θ(n!) 其中k>j>2, b>a>1. 若复杂度函数g(n)所在类别位于f(n)所在类别的左侧,则g(n)∈o(f(n))
    7. [线性组合]若c≥0, d>0, g(n)∈O(f(n)), 且h(n)∈Θ(f(n)),则c×g(n)+d×h(n)∈Θ(f(n))

1.4.3_利用极限计算阶

  1. [P24]例1.26的证明。

1.5_本书概要

1.6_习题

所有的题目我都看过了,比较有意义的是下列题目,推荐大家完成。未来我将补上以下习题的我的答案:

  1. [1.1节]#3,6-7
  2. [1.3节]#10-11,14
  3. [1.4节]#22-27
  4. [补充习题]#29-32,34-44