第十七課：數據結構上(已修改)
2024-10-14 13:04 本頁面
【正文】 第十七課：數據結構 (上 ) 周甫 學習目標 各種常用算法、排序算法的掌握 1 遞歸算法 2 快速排序算法 3 1 算法 (algorithm) ?什么是算法 ? 對一個現有的問題我們采取的解決過程及方法 ,即為算法 . 一個用算法實現的程序會耗費兩種資源：處理時間和內存。 ?算法的效率分析標準 ?簡單性和清晰度 ?空間效率 ?時間效率 ?算法的類型 ? 貪婪算法 (greedy algorithm) ? 分治算法 (divideandconquer algorithm) ? 回溯算法 (backtracking algorithm) ?計算增長率的方式 ? 通過 ()方法來測試 * 缺點： ，測試時間會變得不切實際！ ? 指令 指編寫算法的代碼 .對一個算法的實現代碼計算執(zhí)行指令次數。兩種類型指令：不管輸入大小，執(zhí)行次數永遠不變；執(zhí)行次數隨著輸入大小改變而改變。一般，我們主要測試后一種指令。 * ? 代碼 1： long end_time = 0。 t1 int testVar = 0。 t2 for (int i = 1。 i = test_data。 i++) t3 { testVar++。 t4 testVar。 t4 } 假設 t1 t4分別代表每條語句的執(zhí)行時間，那么，以上代碼的總執(zhí)行時間為： t1 + t2 + n(t3 + 2t4).其中 n = test_data,當 test_data增大時， t1和 t2可以忽略不計，也就是說，對于很大的 n,執(zhí)行時間可以近似于： n(t3 + 2t4) ? 一個算法中包含的對象和引用的數目，越多則內存使用越高，反之越低 ?比較增長率 ? 條件 1： c≦ f(n)/g(n) ≦ d (其中 c和 d為正常數， n代表輸入大小 ) 當滿足以上條件 1時，則 f(n)和 g(n)具備相同的增長率，或者兩函數復雜度的階相同！ 如： f(n) = n + 100 和 g(n) = + 10 上兩函數就具備相同的增長率。 條件 2： 當 n增大時， f(n)/g(n)趨向于 0 當滿足此條件 2時，則該兩個增長函數有不同的增長率。 比如： f(n) = 10000n + 20200 和 g(n) = n?2 + n + 1 。請比較以上兩函數增長率是否一樣，如果不一樣，誰的增長率小？ ? O表示法 如果 f的增長率小于或者等于 g的增長率，則我們可以用如下的大 O表示法： f = O(g) O表示 on the order of
教學課件相關推薦
鄂ICP備17016276號-1