《算法設(shè)計與分析》PPT課件

算法設(shè)計與分析 排序問題將數(shù)據(jù)集合中的數(shù)據(jù)按從小到大的順序重新排列.這是計算機科學(xué)中產(chǎn)生豐富算法的領(lǐng)域插入,選擇,冒泡,快速,歸并,. Python列表類型提供了方法.sort() 樸素策略:選擇最小值思想:每次從剩下的數(shù)據(jù)中選擇最小值輸出.如何求一批數(shù)據(jù)的最小值?逐個檢查數(shù)據(jù),記下當(dāng)前最小值.最小值輸出如果數(shù)據(jù)集合是列表,則第一次最小值放入0號單元,第二次最小值放入1號單元,. 選擇排序算法代碼def selSort(list): n = len(list) for i in range(n-1): # 求listi.listn-1間的最小值 min = i # 初始i為當(dāng)前最小 for j in range(i+1,n): # 與后面值比大小 if listj 1: m = n / 2 list1,list2 = datalist:m,datalistm: mergeSort(list1) mergeSort(list2) merge(list1,list2,datalist) 算法的優(yōu)劣比較對同一問題可設(shè)計多種算法,如何比較優(yōu)劣?正確性不是唯一標(biāo)準(zhǔn)耗費的時間(和空間)很重要!經(jīng)驗分析:比較電腦上實際運行時間依賴于平臺算法分析:分析算法代碼,估算解題所耗步數(shù)(時間).步數(shù)越多,時間越長平臺無關(guān) 12 算法復(fù)雜度算法復(fù)雜度與問題數(shù)據(jù)量(規(guī)模)有關(guān)常用n表示問題規(guī)模算法復(fù)雜度是n的函數(shù)尤其關(guān)心當(dāng)n越來越大時,算法復(fù)雜度會如何變化def f1(): def f2(): def f(n): x=0 x=0 x=0 for i in range(10): for i in range(20) for i in range(n): x=x+1 x=x+1 x=x+1 大O表示法根據(jù)函數(shù)的增長率特性來刻畫函數(shù)令f(n)和g(n)是兩個函數(shù),如果存在正常數(shù)c使得只要n足夠大(例如n n0), 則記為)()( ngcnf )()( ngOnf 15 搜索算法的比較線性搜索步數(shù)與n成正比:O(n)稱為線性時間算法二分搜索步數(shù)與log2 n成正比:O(log2 n)或O(log n)稱為對數(shù)時間算法猜數(shù)游戲中:若數(shù)的范圍是11000000,則線性策略:平均要猜50萬次才能猜對最壞1百萬次,最好1次二分搜索:最壞也只需猜20次 排序算法的比較選擇排序每次循環(huán):從剩余數(shù)據(jù)中選擇最小值,所需步數(shù)為剩余數(shù)據(jù)的個數(shù)步數(shù): n+(n-1)+.+1 = n(n+1)/2稱為二次方時間算法:O(n2)歸并排序每層歸并都涉及n步共有l(wèi)og 2n層nlog2n時間算法:O(nlogn) H anoi塔算法難度:需要2n 1步!指數(shù)時間算法:O(2n)根據(jù)H anoi塔的傳說:有64個金盤.就算僧侶1秒移動一次,至少也要花 2 641秒,大約等于5850億年. 12 122.22. 122)3(2 12)2(2 1)1(2 )1(1)1()( 221 232 n nn nf nfnf nfnfnf 各種復(fù)雜度的比較如圖 可計算性問題可劃分為:可計算的:存在確定的機械過程,一步一步地解決問題.可計算,而且能有效解決可計算,但難度太大,不能有效解決不可計算的:不存在明確的機械過程來求解該問題.不可解,不可判定 停機問題能否編一個終止性判定程序H ALT?def H ALT(prog,data) 若prog(data)終止,則輸出True;否則輸出False.是不可解(unsolvable)問題!若存在H ALT,則歌德巴赫猜想可以迎刃而解:def gc(): n = 2 while True: if 2*n 不是兩個素數(shù)的和,則返回False n = n + 1然后運行H ALT(gc)即可. 哥 德 巴 赫 猜 想 主 張 每 個 大 於 等 於 4的 偶 數(shù) 都 是 哥 德 巴赫 數(shù) 可 表 示 成 兩 個 質(zhì) 數(shù) 之 和 的 數(shù) 停機問題(續(xù))說H ALT不存在只能通過嚴格證明:假設(shè)存在H ALT(prog,data). 則編程序def strange(p): result = H ALT(p,p) if result = True: #即p(p)終止 while True: pass else: return運行strange(strange),結(jié)果如何? 22 End