最大投资回报问题：暴力解法 下面的过程遍历的顺序为： (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) MaxSum =0; for (i=0;i<N;i++) the sequence ThisSum=0; =0 for (j=i;j N;j++) 1 =2 ThisSum+=A[j]; 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 or: 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-SUBARRAY(A,low,high) 非递归代价：常量 1 if high ==low 2 return (low,high,Allow /base case:only one element 3 else mid =[(low +high)/2] 4 (left-low,lefi-high,left-sum)= 递归，理想状况下 FIND-MAXIMUM-SUBARRAY(A,low,mid) 问题规模是原来的 5 (right-low,right-high,right-sum)= 一半。 FIND-MAXIMUM-SUBARRAY(A,mid +1.high) 非递归代价： 6 (cross-low,cross-high,cross-sum)= 线性 FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) 7 if left-sim≥right-sumn and left-sm≥cross-sm 8 return (lef-low,lef-high,lefi-sum) 9 elseif right-sum z left-sum and right-sum z cross-sum 非递归代价： 10 return(right-low,right-high.right-sum) 常量 11 else return (cross-low.cross-high,cross-sum) O(nlog n
非递归代价：常量 递归，理想状况下 问题规模是原来的 一半。 非递归代价： 线性 非递归代价： 常量 O(nlogn)
矩阵乘法：似乎非得2(m) fA=(a）and B=(b)are square nx nmatrices,then in the product C=A.B,we define the entry cij,for i.j=1.2.....n,by SQUARE-MATRIX-MULTIPLY (A,B) 1 n=A.rows c=∑ak·be 2 let C be a new n x n matrix 3 for i 1 to n k三1 4 for j Iton 5 C)=0 6 for k 1ton 7 C时=Cj十ak·bk对 8 return C
矩阵乘法：似乎非得(n 3 )
问题：你能就以下这句话，说清楚2，©，O和0 的区别吗？ 不会比n3小 You might at first think that any matrix multiplication algorithm must take (n3) time,since the natural definition of matrix multiplication requires that many mul- 定 tiplications.You would be incorrect,however:we have a way to multiply matrices 比 in o(n3)time.In this section,we shall see Strassen's remarkable recursive algo- rithm for multiplying n x n matrices.It runs in (ng)time,which we shall show in Section 4.5.Since lg 7 lies between 2.80 and 2.81,Strassen's algorithm runs in 小 O(n281)time,which is asymptotically better than the simple SQUARE-MATRIX- MULTIPLY procedure
问题：你能就以下这句话，说清楚Ω,Θ,О和o 的区别吗？ 不会比n 3小 一 定 比 n 3 小