Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks
算法导论 - 算法入门 ,一小节(插入排序,复杂度)
#  插入排序                -         复杂度
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>=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>=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
posted on 2009-11-18 23:29 刘凯毅 阅读(1563) 评论(0)  编辑  收藏 所属分类: python算法/函数

只有注册用户登录后才能发表评论。


网站导航: