算法业计与分祈 k ◆forj←1tok ◆sum[j]←0 ◆fori←-1toj2 sum[←sum[j+1 end for ◆ end for ◆ Return sum[1..k 算法设计与分析
算法设计与分析 31 w k← w for j ←1 to k w sum [j] ←0 w for i ←1 to j2 w sum [j] ←sum [j]+i w end for w end for w Return sum[1…k] n
算法业计与分祈 运算频度 ◆fori<2ton X<a i k← modbinaryserch(A[1…-1],x) ◆forj←i- 1 downto k A[i+1]←Aj end for A[k]←x ◆ End for 32 算法设计与分析
算法设计与分析 32 运算频度 w for i ←2 to n w x ←A [i] w k ←modbinaryserch(A[1…i-1],x) w for j ←i-1 downto k w A[j+1] ←A [j] w end for w A [k] ←x w End for
算法计与分析 执行步数 ◆TSum(Ta[,intn)000 00 0 ◆ T tsum=0; for(int 1=0 K<n; 1++) 1 n+1 n+1 多入m+吗 n n s◆ return tsum; 00 0 总计2n+3 33 算法设计与分析
算法设计与分析 33 执行步数 w T Sum(T a[], int n) 0 0 0 w { 0 0 0 w T tsum = 0; 1 1 1 w for(int i=0;i<n;i++) 1 n + 1 n + 1 w tsum += a[i]; 1 n n w return tsum; 1 1 1 w } 0 0 0 w 总计2 n + 3
算法计与分析 T Rsum(tall, int n)000 ◆{000 ◆if(n>0)1n+1n+ return Rsum(a, n-1)+an-1; Inn 人, return0111 ◆}000 ◆总计2n+2 34 算法设计与分析
算法设计与分析 34 w T Rsum(T a[], int n) 0 0 0 w { 0 0 0 w if(n> 0) 1 n + 1 n + 1 w return Rsum(a,n-1) + a[n-1]; 1 n n w return 0; 1 1 1 w } 0 0 0 w 总计2 n + 2
算法业计与分祈 运算频度 ◆prod←-1;sum<0 ◆forj←1tok prod←prod×A[j ◆ end for 多A+forj←k+1ton Sum←Sum+A[j End for 算法设计与分析
算法设计与分析 35 运算频度 w prod ←1;sum ←0 w for j ←1 to k w prod ←prod ×A [j] w end for w for j ←k+1 to n w sum ←sum + A [j] w End for