算法设计与分析-第1章-概述2.pdf

: .
; // c6 sum of (ti-1)
}
a[j+1]=key; // c7 n-1
}
/*插入到正确的位置*/
}
6n−1 n−1 n−1
T(n) = c1n + c2 (n −1) + c3 (n −1) + c4 ∑ti + c5 ∑(ti −1) + c6 ∑(ti −1) + c7 (n −1)
i=1 i=1 i=1
„ 在最好情况下，ti=1, for 1 ≤ i <n;
Tmin (n) = c1n + c2 (n −1) + c3 (n −1) + c4 (n −1) + c7 (n −1)
= (c1 + c2 + c3 + c4 + c7 )n − (c2 + c3 + c4 + c7 ) = O(n)
„ 在最坏情况下，ti = i+1, for 1 ≤ i <n; 输入数组按逆序
n−1 排列
n(n +1) n−1 n(n −1)
(i +1) = −1 i =
∑ 2 ∑
i=1 i=1 2
Tmax (n) ≤ c1n + c2 (n −1) + c3 (n −1) +
⎛ n(n +1) ⎞ ⎛ n(n −1) ⎞ ⎛ n(n −1) ⎞
c4 ⎜ −1⎟ + c5 ⎜ ⎟ + c6 ⎜ ⎟ + c7 (n −1)
⎝ 2 ⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
c4 + c5 + c6 2 ⎛ c4 − c5 − c6 ⎞
= n + ⎜c1 + c2 + c3 + + c7 ⎟n − (c2 + c3 + c4 + c7 )
2 ⎝ 2 ⎠
= O(n2 ) 7算法分析方法－举例
„ 对于输入数据a’[i]=n-i,i=0,1,…,n-1，算法insertion_sort 达到其
最坏情形。
8算法分析方法－举例
INSERTION-SORT(A)
1for( j = 2; j <=length[A]; j++) // loop header
2{ key = A[j]
3 // Insert A[j] into the sorted sequence A[1 .. j-1]
4 i←j-1
5 while( i > 0 && A[i] > key)
6{A[i+1] = A[i]
7 i = i-1
8}
9 A[i+1] = key
10 } // loop body below
9
9规律：总是位于
算法的最内层循
环中
分析非递归算法的通用方案
„ 1、决定用哪