计算机问题求解 – 论题2-02 - 算法的效率 2018年03月14日

问题1：你如何理解这里的“优化”？算法级？程序级？

问题2：以下两个程序，在执行效率上有什么区别？ 对一个二维数组A[m,n]进行遍历： 程序1： for I from 1 to M do for J from 1 to N do do something with A[I,J] 程序2： A[1,1] A[1,2] A[1,3] A[1,4] A[1,5] A[1,6] A[1,7] … A[2,1] A[2,2] A[2,3] A[2,4] A[2,5] A[2,6] A[2,7] 基于空间局限性原理，对顺序序列来说，如果数据块被访问就意味着该数据块之后的数据很快就会被访问， IBL （Infinite-Block Look-ahead）技术每次预取数据块 i 后的 n（预取度）个页面

给定一个算法，什么样的优化算是质上的优化？ 问题3： 你能说出如何用Linear Search算法搜索一个未排序 的序列吗？书中给出的优化方法是什么？这种优化 是量上的优化还是质上的优化？？ 给定一个算法，什么样的优化算是质上的优化？ 将待搜对象放到序列末位，确定不会越界。省去循环中的每次结束判断，节省几乎一半时间。 空间换时间。

问题4： “算法分析”主要是干什么？ 优化一个算法： 首先要完成算法“性能”的度量，依此判定算法的优劣； 度量一个算法的性能，首先要给出描述算法性能的模型 代价是什么？ 计算机运行时，主要的代价就是时间和占用的空间，其中时间又是更为重要的 算法的渐进时间复杂度模型

一个插入排序方法

在“插入每张牌前，手上的牌都是已经排好序的” 插入法： 在“插入每张牌前，手上的牌都是已经排好序的”

范例 总是已经排好序的片段 总是已经排好序的片段

提请注意：你应该会证明这个算法的正确性！ 伪代码 提请注意：你应该会证明这个算法的正确性！

算法的性能度量模型 算法性能涉及 算法的时间复杂度模型 空间性能（空间复杂度） 时间性能（时间复杂度） 执行指令条数的统计模型：数数字！ 算法在给定合法输入的情况下，要消耗多少“临时”存储空间 局部变量、过程调用的堆栈空间等 特定场合中较为关注 时间性能（时间复杂度） 算法在给定合法输入的情况下，需要执行多少时间 重点关注内容！ 算法的时间复杂度模型 执行指令条数的统计模型：数数字！

数数字！

性能评估函数 一个N上的函数 问题5：我们能用一个具体的数值来表示算法的效率吗？如果不能，我们该用什么？

Best case

Worst case best case和worst case两种结果中，更重要的是哪个？ 既然有best case和worst case，有average case吗？如果有，会如何进行average case的分析？ 我们需要对一个算法的语句的执行条数进行统计，但我们需要如此精确地进行统计吗？

Average case

这样子的时间复杂度函数难于使用！ 1，过于复杂，细节太多，影响理解本质 2，没有必要，可以“省略”

往往是：我们可以容忍我们的某种程度上的“粗心”： 渐进分析方法： 渐近分析是一种描述函数在极限附近的行为的方法 我们观察算法的时间复杂度，重点关注的就是在处理规模不断增大时的时间性能表现 渐进分析方法

Maximum solvable input size (approx.) 两个不同算法的优劣关键是”增长率” Algorithm 1 2 3 4 5 Time function(ms) 33n 46n lg n 13n2 3.4n3 2n Input size(n) Solution time 10 0.00033 sec. 0.0015 sec. 0.0013 sec. 0.0034 sec. 0.001 sec. 100 0.0033 sec. 0.03 sec. 0.13 sec. 3.4 sec. 41016 yr. 1,000 0.033 sec. 0.45 sec. 13 sec. 0.94 hr. 10,000 0.33 sec. 6.1 sec. 22 min. 39 days 100,000 3.3 sec. 1.3 min. 1.5 days 108 yr. Time allowed Maximum solvable input size (approx.) 1 second 30,000 2,000 280 67 20 1 minute 1,800,000 82,000 2,200 260 26

鉴于此，我们可以容忍我们的某种程度上的“粗心” 我们往往忽略不同语句的执行开销差异并标准化 C1=C2=…=C8 渐进分析方法 T(n)=1.5n2+3.5n-4

鉴于此，我们可以容忍我们的某种程度上的“粗心” 我们往往忽略多项式中的“小项” 我们往往忽略 “系数”而只保留其指数 T(n)~1.5n2+3.5n-4 T(n)~1.5n2 渐进分析方法 T(n)~n2

鉴于此，我们可以容忍我们的某种程度上的“粗心” 我们选择“代表性”语句，进行统计 哪些是代表性的语句？ K2当中的某个代表性的操作语句 根据任务性质选择代表性语句 排序算法中的比较操作 本质上，排序就是消除逆序对 渐进分析方法

完成这个判断，也必须建立数学系统，给出“好”的定义，进行科学判断 插入排序：best case是n级别的；worst case是n2级别的。 归并排序：worst case是nlgn级别的 哪个算法“好”呢？ 完成这个判断，也必须建立数学系统，给出“好”的定义，进行科学判断

集合 “Big Oh” f(n)长得不比g(n)快 问题：你能结合右图解释c和n0的含义吗？ f(n)长得不比g(n)快

如何理解常数c？ g(n)

100n+200和nlogn哪个快？ 100n+200 nlogn

集合 “Θ”、“Ω”

函数增长率的比较 g Ω(g): 该集合中任一函数的增长率不低于g的增长率（至少与g增长得一样快！）

以下式子代表什么含义？ T(n)=2n2+O(n)=2n2 =O(n2) T(n)=2n2+Θ(n)=2n2 = Θ(n2)

算法的时间复杂度性能评估模型 一个统计模型 一个重点关注worst case的统计模型 一个渐进统计模型 基于问题规模而渐进 一个用渐进函数的上界函数进行“标定”的统计模型 渐进分析法最常用的表示方法是用于描述函数渐近行为的数学符号，更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。

实际上，我们可以用下式来判断： 函数 f 是Ο(g) if limn→[f(n)/g(n)]=c< if there exists constants c R+ and n0 N such that for all n(n>=n0), f(n)cg(n) Let f(n)=n2, g(n)=nlgn, then: fΟ(g), since gΟ(f), since nlgnO(n2) 如何用极限方式判断f是否属于Θ(g)?

对数函数与幂函数 Which grows faster? So, log2nO( )

lgn  o(n) for any >0 一般性结论 The log function grows more slowly than any positive power of n lgn  o(n) for any >0 By the way: The power of n grows more slowly than any exponential function with base greater than 1 nk  o(cn) for any c>1

给定一个算法，什么样的优化算是质上的优化？ 问题6： 给定一个算法，什么样的优化算是质上的优化？

Open topic1： 什么是“Algorithmic Gap”?请你任意举一个算法问题案例，证明这个算法问题的Algorithmic Gap已经被弥合 首先弄清楚两个概念：算法问题、解这个问题的算法； 算法问题P的难度是固有的，假设是g；这个g是我们竭力想知道，但往往我们却难以认识到。 当我们找到一个解这个问题的算法时（假设它的性能是f），我们可以说：g属于order of f。f 是算法问题难度的上界之一；当我们不断优化算法得到f’,f’’，……时，算法问题的难度上界不断降低（order级别的降低） 但是，仅仅降低上界，不能得到g。 同时，如果我们能够证明，解这个算法问题，至少需要order of h的算法才可以，比如遍历的难度至少是O(n)，那么我们就得到了算法问题的一个难度的下界。那么我们在这个方向上的工作就是不断去证明：问题P的解的最小代价是否比h高，得到下界h’,h’’。 如此，问题P的解的下界不断在提高（用证明来完成），问题P的解的上界不断在下降（用算法设计来完成），如果他们meet了，我们可以说：我们找到了这个问题P的解的难度g；否则，h’’’和f’’’之间的gap就存在，就被称为这个问题的算法gap。 当算法gap存在时，要么就是我们没有找到最好的算法，要么就是我们不能证明还有其它更好的算法（无法证明现在的算法不能再好了），要么就是两者都没有完成。

Open topic2: 大O（ Θ ，Ω）和小o(θ,ω)有什么区别？