【正文】 ndigit integers, and shift to obtain result. DivideandConquer Multiplication: Warmup ??T( n ) ? 4 T n / 2? ?r e c u r s i ve c a l l s ? ? ( n )a dd , s h i f t ? T ( n ) ? ? ( n 2 ) ??x ? 2 n / 2 ? x 1 ? x 0y ? 2 n / 2 ? y 1 ? y 0xy ? 2 n / 2 ? x 1 ? x 0? ? 2 n / 2 ? y 1 ? y 0? ? ? 2 n ? x 1 y 1 ? 2 n / 2 ? x 1 y 0 ? x 0 y 1? ? ? x 0 y 0assumes n is a power of 2 42 To multiply two ndigit integers: ? Add two 189。 22 規(guī)則 O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的 證明： 對于任意 f1(n) ? O(f(n)) ，存在正常數(shù) c1和自然數(shù) n1，使得對所有 n? n1，有 f1(n) ? c1f(n) 。 （ 1） 漸近上界記號 O O(g(n)) = { f(n) | 存在正常數(shù) c和 n0使得對所有 n? n0有： 0 ? f(n) ? cg(n) } （ 2） 漸近下界記號 ? ?(g(n)) = { f(n) | 存在正常數(shù) c和 n0使得對所有 n? n0有： 0? cg(n) ? f(n) } （ 3） 緊漸近界記號 ? ? (g(n)) = { f(n) | 存在正常數(shù) c1,c2和 n0使得對所有 n? n0有： c1g(n) ? f(n) ? c2g(n) } 如果 f(n) 集合 O(g(n))中的一個成員， 我們說 f(n) 屬于 O(g(n))。這位聰明的大臣的胃口看來并不大，他跪在國王面前說： “ 陛下，請您在這張棋盤的第一個小格內(nèi)，賞給我一粒麥子；在第二個小格內(nèi)兩粒，第三個給四粒，照這樣下去，每個小格內(nèi)都比以前一個小格加一倍。最后大家拿了許多袋麥子過來都只完成了一小部分的填充工作，大家這才感覺到問題的嚴重。原因？沒有原因，習慣問題而已。t overlap. ? Goal: find maximum subset of mutually patible jobs. Time 0 1 2 3 4 5 6 7 8 9 10 11 f g h e a b c d 31 Interval Scheduling: Greedy Algorithms Greedy template. Consider jobs in some order. Take each job provided it39。t use inpatible jobs { p(j) + 1, p(j) + 2, ..., j 1 } – must include optimal solution to problem consisting of remaining patible jobs 1, 2, ..., p(j) ? Case 2: OPT does not select job j. – must include optimal solution to problem consisting of remaining patible jobs 1, 2, ..., j1 ??O P T ( j ) ? 0 i f j ? 0m a x vj ? O P T ( p ( j )), O P T ( j ? 1 )? ? o t h e r w i s e??????optimal substructure 52 Input: n, s1,…,sn , f1,…,fn , v1,…,vn Sort jobs by finish times so that f1 ? f2 ? ... ? fn. Compute p(1), p(2), …, p(n) ComputeOpt(j) { if (j = 0) return 0 else return max(vj + ComputeOpt(p(j)), ComputeOpt(j1)) } Weighted Interval Scheduling: Brute Force Brute force algorithm. 53 Weighted Interval Scheduling: Brute Force Observation. Recursive algorithm fails spectacularly because of redundant subproblems ? exponential algorithms. Ex. Number of recursive calls for family of layered instances grows like Fibonacci sequence. 3 4 5 1 2 p(1) = 0, p(j) = j2 5 4 3 3 2 2 1 2 1 1 0 1 0 1 0 54 Input: n, s1,…,sn , f1,…,fn , v1,…,vn Sort jobs by finish times so that f1 ? f2 ? ... ? fn. Compute p(1), p(2), …, p(n) for j = 1 to n M[j] = empty M[0] = 0 MComputeOpt(n) { if (M[n] is empty) M[n] = max(vn + MComputeOpt(p(n)), MComputeOpt(n1)) return M[n] } global array Weighted Interval Scheduling: Memoization Memoization. Store results of each subproblem in a cache。s. Structural. Discover a simple structural bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound. Exchange argument. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality. Other greedy algorithms. Kruskal, Prim, Dijkstra, Huffman, … 37 Coin Changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex: 34162。 18 漸近分析中函數(shù)比較 f(n)= O(g(n)) ? a ? b。 哪個算法好？ 就算都是多項式，也需表現(xiàn)差異 若算法 A運行 n2+100n步，算法 B運行 2n2步。Design and Analysis of Algorithms 2. Basics of algorithm design amp。很多問題很容易就可以給出一個指數(shù)運行時間的窮舉搜索算法，但是否都存在多項式算法？（ 計算機科學的核心問題 ） 是否每個多項式時間的算法都有效？ 10 數(shù)量級的差別 對于一個輸入為 n的問題，現(xiàn)給出兩個算法 A和 B. 算法 A運行 100n步，算法 B運行 nlogn步。 等式和不等式中漸近記號 O,o, ?和 ?的意義是類似的。s see what happens. ? Let i1, i2, ... ik denote set of jobs selected by greedy. ? Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. . . . Greedy: OPT: solution still feasible and optimal, but contradicts maximality of r. ir+1 job ir+1 finishes before jr+1 36 Greedy Analysis Strategies Greedy algorithm stays ahead. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm39。 lookup as needed. 55 Weighted Interval Scheduling: R