最大投资回报问题:暴力解法 下面的过程遍历的顺序为: 00,(0,1),…,(0,m-1);(1,1),(1,2)…,(1,1-1,….(2m2,、(2,n1,、(1+1) MaxSum=0 for(i=0; i<N; i+ the sequence This Sum=0 for (=i;j<N;j++) ThisSum +=An if(ThisSum > MaxSum) MaxSum= thissum in O(n2) 户=n-1 return MaxSum
最大投资回报问题：暴力解法 MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; the sequence i=0 i=1 i=2 i=n-1 j in O(n2 ) 下面的过程遍历的顺序为： (0,0), (0,1), …, (0,n-1); (1,1), (1,2), …, (1,n-1), …… (n-2,n-2), (n-2, n-1), (n-1,n-1)
用分治法解最大子数组问题 Part 1 Part 2 the sub with largest sum may be in recursion Part 1 Part 2 The largest is the result Part 1 Part 2 问题5:跨中点的部分如何计算?
用分治法解最大子数组问题 Part 1 Part 2 the sub with largest sum may be in: Part 1 Part 2 or: Part 1 Part 2 recursion The largest is the result
FIND-MAXIMUM-SUB ARRAY(A, low high) I if high == low 非递归代价:常量 3 else mid=[(low high)/2 4(lef-low, Ief-high, Ilefi-sum)= 递归,理想状况下 FIND- MAXIMUM- ST问是规楼界来的 = MAXIMUM-SUBARRAY(A, mi+.非归代价 6 (cross-low, cross high, cross-s1n)= 线性 FIND-MAX-CROSSING-SUBARRAY (A, low, mid, high) 7 if lef-sum 2 righ-stumn and lef-sum 2cross-stum 8 return(lefi-low, lef-high, lefi-sum) 非递归代价: 10 return (right-low, right-high, right-sum) 常量 ll else return(cross low, cross high, cross-sum) Olog n
非递归代价：常量 递归，理想状况下 问题规模是原来的 一半。 非递归代价： 线性 非递归代价： 常量 O(nlogn)
矩阵乘法:似乎非得D) If A=(ai B=(; )ane square n X n matrices, then in the product C =A. B, we define the c1.2.,.by SQUARE- MATRIX-MULTIPLY(A, B) I n=A.rows ∑ab 2 let c be a new nx nmatriⅸ 3 for i=l ton k=1 4 forj=l ton 567 Ci;=0 fork= 1 to n G=G+ak·b 8 return C
矩阵乘法：似乎非得(n 3 )
问题:你能就以下这句话,说清楚Ω,⊙O和o 的区别吗? 不会比n3小 You might at first think that any matrix multiplication algorithm must take &2(n). time, since the natural definition of matrix multiplication requires that many mul- rE tiplications. You would be incorrect, however: we have a way to multiply matrices in o(n)time. In this section, we shall see Strassen's remarkable recursive algo- rithm for multiplying n X n matrices. It runs in O(n g )time, which we shall show in Section 45. Since lg 7 lies between 2, 80 and 2, 8l. Strassen's algorithm runs in O(n2.)time, which is asymptotically better than the simple SQUARE-MATRIX MULTIPLY procedure
问题：你能就以下这句话，说清楚Ω,Θ,О和o 的区别吗？ 不会比n 3小 一 定 比 n 3 小