[農學]第1章緒論-資料下載頁
2025-10-07 17:48本頁面
【正文】 論： 注意引用如下關系式： n=bm， m=logbn, am=alogbn =nlogba (1) r1： ? ri 1/(1r)，由于 am=nlogba，所以， T(n)=O(nlogba)； (2)r=1： ? ri=m+1=logbn+1，由于 am =nlogba= nk，所以， T(n)=O(nk logbn)； (3)r1： ? ri =(rm+11)/(r1)=O(rm)，所以， T(n)=O(amrm)=O(bkm)=O(nk) 算法設計與分析 ? ? ? ? ? = = k k k b k k a b a n O b a n n O b a n O n T b ) ( ) log ( ) ( ) ( log 算法設計與分析 算法的后驗分析 算法的后驗分析（ Posteriori）也稱算法的實驗分析，它是一種事后計算的方法，通常需要將算法轉換為對應的程序并上機運行。 算法設計與分析 一般步驟： 1. 明確實驗目的 2. 決定度量算法效率的方法 ， 為實驗準備算法的程序實現(xiàn) 3. 決定輸入樣本，生成實驗數(shù)據(jù) 4. 對輸入樣本運行算法對應的程序 ， 記錄得到的實驗數(shù)據(jù) 5. 分析得到的實驗數(shù)據(jù) 算法設計與分析 表格法記錄實驗數(shù)據(jù) 129,799 113,063 91,274 78,692 67,272 53,010 39,992 24,303 11,966 次數(shù) 9000 8000 7000 6000 5000 4000 3000 2021 1000 規(guī)模 散點圖記錄實驗數(shù)據(jù) 執(zhí) 行 次 數(shù) 或 時 間 問題規(guī)模 n 算法設計與分析 作業(yè) ? 習題 1 ? 使用擴展遞歸技術求解（ 1），使用通用分治遞推式求解（ 2） ? 12 ? 13 算法設計與分析 實驗項目 —— 求最大公約數(shù) 1. 實驗題目 求兩個自然數(shù) m和 n的最大公約數(shù) 。 2. 實驗目的 ⑴ 復習數(shù)據(jù)結構課程的相關知識 ， 實現(xiàn)課程間的平滑過渡； ⑵ 掌握并應用算法的數(shù)學分析和后驗分析方法； ⑶ 理解這樣一個觀點：不同的算法能夠解決相同的問題 ， 這些算法的解題思路不同 ， 復雜程度不同 ， 解題效率也不同 。 算法設計與分析 3. 實驗要求 ⑴ 至少設計出三個版本的求最大公約數(shù)算法； ⑵ 對所設計的算法采用大 O符號進行時間復雜性分析； ⑶ 上機實現(xiàn)算法 ， 并用計數(shù)法測算算法的運行時間； ⑷ 通過分析對比 ， 得出自己的結論 。
教學課件相關推薦
鄂ICP備17016276號-1