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