计算机问题求解 – 论题1-14 - 算法的效率 2018年12月18日

Part I 算法的时间代价

问题1: Hanoi Tower的递归算法 无疑是正确的, 但你认为它 是“可接受的”吗？

需要移动多少次圆盘？ 相应的递归方程是： T(n) = 2T(n-1)+1 即：T(n) = 2n-1 其数量级大约是 1019，即1000亿亿！ 如果每秒移动1亿个盘子，需要大约3200年！

问题2： 现在你是否理解对一个问题找 到一个正确的算法并不等同于 我们“能”解这个问题了呢？

TSP: (也许是)世界上最具挑战性的（算法）问题。 Rules that give a number of trials below the number of permutations of the given points are not known!

这年头，我们当然使用计算机… 假设我们使用… 解决33city-TSP… IBM Roadrunner Cluster (美国能源部） 129,600个处理器，每秒执行1457万亿次算数运算 价值1亿3千3百万美元 2009年高性能计算机500强第一名 解决33city-TSP… 耐心等待…请勿关机… We would then need roughly 28 trillion years to solve the 33-city TSP on the Roadrunner, an uncomfortable amount of time, given that the universe is estimated to be only 14 billion years old.

问题  实例

TSP – 挑战计算思维能力的极限

问题3: 为什么我们希望了解计算的 “代价”，而“代价”的关 键就是是什么？

问题4： 为什么我们不能用一个数 值表示算法的“代价”？

一个例子 – 找序列中的最大元素

如果我们关心A的值： 显然：与实际输入有 关； 最小值：0； 最大值：n-1; 平均值：???

“最坏情况”也不一定容易看出来 Euclid(int m,n) if n=0 then return m For any integer k1, if m>n1 and n<Fk+1, then the call Euclid(m,n) makes fewer than k recursive calls. (to be proved) Since Fk is approximately , the number of recursive calls in Euclid is O(lgn). Euclid(int m,n) if n=0 then return m else return Euclid(n, m mod n) measured by the number of recursive calls

问题5: 计算机总会越来越快，我们 也会找到更聪明的算法，代 价问题会一直很重要吗？

Part II 增长率与复杂性

Maximum solvable input size (approx.) 关键是“增长率” Algorithm 1 2 3 4 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

问题6： 增长率怎么表示？

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

集合 “Big Oh” Definition A function fΟ(g) if Giving g:N→R+, then Ο(g) is the set of f:N→R+, such that for some cR+ and some n0N, f(n)cg(n) for all nn0. A function fΟ(g) if Note: c may be zero. In that case, f(g), “little Oh”

一个例子 Let f(n)=n2, g(n)=nlgn, then: fΟ(g), since gΟ(f), since Using L’Hopital’s Rule Let f(n)=n2, g(n)=nlgn, then: fΟ(g), since gΟ(f), since For your reference: L’Hôpital’s rule with some constraints

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

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

问题7： Big-O 的“Robustness” 是什么意思？

问题8： 为什么有时候Big-O可能误导人？

问题9： 你能说出用Linear Search算 法搜索一个未排序的序列的代 价吗？它是否是“最优”的， 为什么？ 顺便问一下：书上讲的优化方法如何实现？

问题10： 什么是“Algorithmic Gap”?

现在说说“平均” 假设要在n个元素的序列中搜索K； 假设K确实在该序列中的概率是q，则不在其中的概率是1-q。 对于特定的位置i (0in-1), 比较次数为i+1。 因此，平均代价是：

问题11： 从Linear Search到Binary Search, 收益是什么？需要付 出什么代价？

如果这里“efficient”是指“线性的”，你的答案满足要求吗？ 考你一下： Let A be an array of integers and S a target integer. Design an efficient algorithm for determining if there exist a pair of indices i,j such that A[i]+A[j]=S. 如果这里“efficient”是指“线性的”，你的答案满足要求吗？ a1 a2 …… ai i Hash(ai) aj If ai = S-aj Hash(S-aj) A

Sleeping Tigers Considered currently 问题12： 你是否还记得有什么非排序算法，其主要代价就是排序的呢？

问题13： 究竟什么样的算法被认为是 “可接受”的呢？

课外作业 DH: pp.153- 6.1 – 6.3 6.10 , 6.11 6.15, 6.16