11-編程的靈魂——數(shù)據(jù)結(jié)構(gòu)算法=程序(完整版)
【正文】 . 大部分算法需要專門設(shè)計 組織和使用數(shù)據(jù) 的方法 . 在計算機科學(xué)中 , 數(shù)據(jù)的組織和使用依靠 數(shù)據(jù)結(jié)構(gòu)(data structure). ? 算法與數(shù)據(jù)結(jié)構(gòu)緊密聯(lián)系 算法的選擇 ? 解決同一個問題 , 通常有多種算法 . – 小規(guī)模問題 (small problems), 各種算法都可以 – 大規(guī)模問題 (large problems), 盡量選擇時間、空間耗費小的算法 . 有時候時間耗費少的空間耗費多 , 則需要根據(jù)實際情況權(quán)衡 (tradeoff) ? 為什么要學(xué)算法設(shè)計 ? – 硬件投資 ? 速度增加 10~100倍 – 算法改進(jìn) ? 一百萬倍的提速相當(dāng)普遍 – 大項目 : 分解為獨立任務(wù) , 有一些關(guān)鍵任務(wù)的算法影響到整個系統(tǒng)的性能 二、算法實現(xiàn)與比較 算法的實現(xiàn) ? 代碼的可重用性 : 一般來說本文盡量調(diào)用已經(jīng)實現(xiàn)好的算法 ? 需要重新實現(xiàn)基本算法的情況 –更好的理解算法 , 為特定應(yīng)用微調(diào)算法 –新計算環(huán)境 , 無庫可用 , 且硬件特性不一致 ? 實現(xiàn)的優(yōu)化程度 : 本文一般只考慮不過分犧牲算法效率下相對自然簡潔的實現(xiàn)方式 ? 真實的實現(xiàn) : 過度優(yōu)化、錯誤處理、維護性 實驗比較 ? 側(cè)重點 –算法分析 : 兩個算法同階 , 只相差一個常數(shù) –實驗比較 : 一個運行 3秒 , 一個運行 30秒 ? 算法分析和實驗比較 –實驗比較可以驗證算法分析的結(jié)果 . 是否真的只相差一個常數(shù) ? –算法分析可以幫助估算實際運行時間 . 愿意等待 10個小時 ? 實驗比較的步驟 ? 步驟一 : 實現(xiàn)算法 . 簡單的算法并不困難 , 但是復(fù)雜的算法的實現(xiàn)具有挑戰(zhàn)性 , 若想得到高效的實現(xiàn)需要關(guān)注一些算法細(xì)節(jié)而不光是編碼細(xì)節(jié) ? 步驟二 : 設(shè)計測試數(shù)據(jù) . 一般來說可以使用實際數(shù)據(jù)、隨機數(shù)據(jù)和特殊 (甚至錯誤 )數(shù)據(jù) . 隨機數(shù)據(jù)保證分析結(jié)果是針對算法而不是數(shù)據(jù)的 , 而特殊數(shù)據(jù)確保算法能正確處理一切給它的輸入 其他 ? 常見錯誤 –不注意程序效率 . 高效算法往往更復(fù)雜 , 但是一但寫成 , 能節(jié)約大量的執(zhí)行時間 –過分注意程序效率 . 常數(shù)時間的優(yōu)化 , 當(dāng)此常數(shù)和基數(shù)都不太大時并不是很必要 ? 實驗比較的附加收獲 –提出的“算法改進(jìn)”真會提高效率嗎 ? –確定待定的參數(shù) 三、算法分析 算法分析的主要任務(wù) ? 任務(wù) –任務(wù)一 : 比較同一問題的不同算法 –任務(wù)二 : 預(yù)測算法在新環(huán)境下的性能 –任務(wù)三 : 設(shè)置算法參數(shù) ? 在很多情況下比”實驗比較”成本低 算法分析的挑戰(zhàn) ? 算法分析的結(jié)果 –情況一 : 透徹的理解 , 精確的公式 –情況二 : 無法得到精確的公式 ? 可能是輸入情況太復(fù)雜 ? 可能是實現(xiàn)細(xì)節(jié)太復(fù)雜 , 難以精確分析 ? 算法分析的基礎(chǔ) : 理想模型 抽象操作 ? 抽象操作 (abstract operations). 對于單一操作 (如加法 )的算法 , 運行時間 = 操作時間 * 操作次數(shù) (不考慮 cache等體系結(jié)構(gòu)方面的影響 ) –操作時間取決于計算機 –操作次數(shù)取決于算法 ? 算法分析 : 只考慮算法特性 , 因此只考慮操作次數(shù) 算法分析的對象 ? 抽象操作數(shù)往往十分巨大 . 一般來說只有少部分操作起主導(dǎo)作用 . 可以用 profile工具檢測中起決定因素的部分 ? 算法分析的對象 : 最經(jīng)常執(zhí)行部分的抽象操作數(shù) (并做適當(dāng)?shù)慕?) 輸入建模 ? 算法分析結(jié)果通常有兩種 –考慮隨機數(shù)據(jù) , 得到平均情況 (averagecase)分析結(jié)果 –考慮最壞數(shù)據(jù) , 得到最壞情況 (worstcase)分析結(jié)果 算法分析的例子 fact := 1。 sum := sum + fact。 算法二（續(xù)） ? 有了 s[i]，怎么快速求 a[i]+…+ a[j]呢？ a[i]+…+ a[j] = (a[1] + … + a[j]) – (a[1] + … + a[i1]) =s[j] – s[i1] 而 s[i]經(jīng)過預(yù)處理以后可以直接讀出！ max := a[1]。顯然存在 不可計算 的函數(shù)。 if s[j] – min_s max then max := s[j] – min_s。 if sum max then max := sum。 for i :=1 to n do for j:=1 to n do sum := sum + a[i,j]。 ? 基本操作：加法 ? 忽略循環(huán)變量 i和 j的改變時間 ? 共 n2次基本操作 復(fù)雜的例子 sum := 0。 end。 end。因此字長不能任意大 . ? 實際機器在 k很小時還提供左移指令計算 2k ? 沒有考慮內(nèi)存的層次關(guān)系，即不考慮 cache和虛擬存儲器 ? 基于 RAM的算法分析主要依靠 : 組合數(shù)學(xué)、概率論、代數(shù)變形以發(fā)現(xiàn)公式中的最高項 △ 并行計算機 ? 機器模型 (Machine Model)與編程模型(Programming Model) ? Flynn分類： SMID和 MMID(Single/Multiple instruction multiple
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1