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