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