算法導論 - 算法入門 ,一小節（插入排序,復雜度）
# 插入排序 - 復雜度
def insertion_sort(arr): # 1
for j in xrange( 1,len(arr) ): # n-1
key = arr[j] # n-1
i=j-1 # n-1
while i>=0 and arr[i]> key : # n(n-1)/2
arr[i+1] = arr[i] # n(n-1)/2
i=i-1 # n(n-1)/2
arr[i+1] = key # n-1
print arr # n-1
驗證結果 :
>>> arr=[5,2,4,6,1,3]
>>> insertion_sort(arr)
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]
驗證復雜度：
z = 5(n-1)+1+3n(n-1)/2
我們測試數據 為 n=6
當數據極端情況就是需要全部重新排列
就是 [6,5,4,3,2,1] 要排出 [1,2,3,4,5,6] 這樣
>> z = 71
一種比較笨的 驗證方法 供大家拍磚 :
def insertion_sort(arr):
ii=0
ii+=1
for j in xrange( 1,len(arr) ):
ii+=1
key = arr[j]
ii+=1
i=j-1
ii+=1
while i>=0 and arr[i]> key :
ii+=1
arr[i+1] = arr[i]
ii+=1
i=i-1
ii+=1
arr[i+1] = key
ii+=1
print arr
ii+=1
print "----",str(ii)
>>> arr=[6,5,4,3,2,1]
>>> insertion_sort(arr)
[5, 6, 4, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
[3, 4, 5, 6, 2, 1]
[2, 3, 4, 5, 6, 1]
[1, 2, 3, 4, 5, 6]
---- 71 #復雜度驗證為 71
羅嗦下 n(n-1)/2
極端情況下
i=1 ; j 需要挪動 1次
i=2 ; j 挪動 1+2次
i=3 ; j 挪動 1+2+3次
....
i=n ; j 挪動 1+2....+n
我們又找到 (1+n)+(2+n-1)+(3+n-2).... = (1+n)n/2
我們這 的 i 是從 2 次開始的 也就是說 (n-1)n/2 了
def tn(ii):
ti=0
for i in xrange(ii) :
for j in xrange(i) :
ti+=1
print ti
print tn(2) #1 = 1
print tn(3) #3 = 1+2
print tn(4) #6 = 1+2+3
..
整理 www.aygfsteel.com/Good-Game
|