《《算法設計與分析》PPT課件》由會員分享，可在線閱讀，更多相關《《算法設計與分析》PPT課件（22頁珍藏版）》請在裝配圖網上搜索。

1、算法設計與分析 排序問題將數據集合中的數據按從小到大的順序重新排列.這是計算機科學中產生豐富算法的領域插入,選擇,冒泡,快速,歸并,. Python列表類型提供了方法.sort() 樸素策略:選擇最小值思想:每次從剩下的數據中選擇最小值輸出.如何求一批數據的最小值?逐個檢查數據,記下當前最小值.最小值輸出如果數據集合是列表,則第一次最小值放入0號單元,第二次最小值放入1號單元,. 選擇排序算法代碼def selSort(list): n = len(list) for i in range(n-1): # 求listi.listn-1間的最小值 min = i # 初始i為當前最小 for j

2、 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)劣比較對同一問題可設計多種算法,如何比較優(yōu)劣?正確性不是唯一標準耗費的時間(和空間)很重要!經驗分析:比較電腦上實際運行時間依賴于平臺算法分析:分析算法代碼,估算解題所耗步數(時間).步數越多,時間越長平臺無關 12 算法復雜度算法復雜度與問題數據量(規(guī)模)有關常用n表示問題規(guī)模算法復雜度是n的

3、函數尤其關心當n越來越大時,算法復雜度會如何變化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表示法根據函數的增長率特性來刻畫函數令f(n)和g(n)是兩個函數,如果存在正常數c使得只要n足夠大(例如n n0), 則記為)()( ngcnf )()( ngOnf 15 搜索算法的比較線性搜索步數與n成正比:O(n)稱為線性時間算法二分搜索步數與log2 n成正比:O(log2 n)或O(log n)稱為

4、對數時間算法猜數游戲中:若數的范圍是11000000,則線性策略:平均要猜50萬次才能猜對最壞1百萬次,最好1次二分搜索:最壞也只需猜20次 排序算法的比較選擇排序每次循環(huán):從剩余數據中選擇最小值,所需步數為剩余數據的個數步數: n+(n-1)+.+1 = n(n+1)/2稱為二次方時間算法:O(n2)歸并排序每層歸并都涉及n步共有l(wèi)og 2n層nlog2n時間算法:O(nlogn) H anoi塔算法難度:需要2n 1步!指數時間算法:O(2n)根據H anoi塔的傳說:有64個金盤.就算僧侶1秒移動一次,至少也要花 2 641秒,大約等于5850億年. 12 122.22. 122)3(2

5、 12)2(2 1)1(2 )1(1)1()( 221 232 n nn nf nfnf nfnfnf 各種復雜度的比較如圖 可計算性問題可劃分為:可計算的:存在確定的機械過程,一步一步地解決問題.可計算,而且能有效解決可計算,但難度太大,不能有效解決不可計算的:不存在明確的機械過程來求解該問題.不可解,不可判定 停機問題能否編一個終止性判定程序H ALT?def H ALT(prog,data) 若prog(data)終止,則輸出True;否則輸出False.是不可解(unsolvable)問題!若存在H ALT,則歌德巴赫猜想可以迎刃而解:def gc(): n = 2 while Tru

6、e: if 2*n 不是兩個素數的和,則返回False n = n + 1然后運行H ALT(gc)即可. 哥 德 巴 赫 猜 想 主 張 每 個 大 於 等 於 4的 偶 數 都 是 哥 德 巴赫 數 可 表 示 成 兩 個 質 數 之 和 的 數 停機問題(續(xù))說H ALT不存在只能通過嚴格證明:假設存在H ALT(prog,data). 則編程序def strange(p): result = H ALT(p,p) if result = True: #即p(p)終止 while True: pass else: return運行strange(strange),結果如何? 22 End