算法导论 - 算法入门 ,一小节（插入排序,复杂度）
# 插入排序 - 复杂度
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.blogjava.net/Good-Game
|