數(shù)據(jù)結(jié)構(gòu)第一章(編輯修改稿)
2024-08-31 16:53 本頁面
【文章內(nèi)容簡介】 59 Such an input sequence is called an instance of the sorting problem ? 算法的特性 ? 有窮性 ? 對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間內(nèi)完成 ? 確定性 ? 每一條指令必須有明確的含義，讀者理解時不會產(chǎn)生二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，相同的輸入只能得出相同的輸出。 算法的特性 ? 算法的特性（續(xù)） ? 可行性 ? 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次來實(shí)現(xiàn)。 ? 輸入 ? 零個或多個輸入。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法中 ? 輸出 ? 一個或多個輸出，與 “ 輸入 ” 有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能 算法的特性 ? 算法 設(shè)計(jì)的原則 ? 正確性 (correctness) ? 可讀性 (readability) ? 健壯性 (robustness) ? 高效率與低存儲量 算法的特性 正確性：算法應(yīng)當(dāng)滿足具體問題的需求 可分為四個層次： 無語法錯誤 、隨意數(shù)據(jù)、 刻意數(shù)據(jù)、一切合法數(shù)據(jù) 可讀性： 算法主要是為了人的閱讀與 交流，其次才是為計(jì)算機(jī)執(zhí)行，因此 算法應(yīng)該易于人的理解；晦澀難讀的 程序易于隱藏較多錯誤而難以調(diào)試 健壯性： 當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng) 恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是 產(chǎn)生莫名奇妙的輸出結(jié)果。處理出錯的方 法也不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回 一個表示錯誤或錯誤性質(zhì)的值，以便在更 高的抽象層次上進(jìn)行處理 高效率與低存儲量： 效率指的是算法執(zhí)行時間；存儲量指 的是算法執(zhí)行過程中所需的最大存儲 空間 ? 解決同一個問題存在多種算法，如何評估各算法的好壞？或據(jù)此設(shè)計(jì)出更好的算法？ ? 運(yùn)行該算法所需要的計(jì)算機(jī)資源的多寡，所需越大復(fù)雜性越高 ? 最重要的資源：時間（處理器）和空間（存儲器） ? 評價一個算法優(yōu)劣的重要依據(jù)是看執(zhí)行該算法的程序需要占用多少機(jī)器資源： ? 程序所用算法運(yùn)行時所要花費(fèi)的時間代價 ? 程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價 算法復(fù)雜度分析 算法復(fù)雜度分析 ? 算法的復(fù)雜度包含： 時間復(fù)雜度 空間復(fù)雜度 ? 主要考慮 時間復(fù)雜度 ? 設(shè)計(jì)算法的目標(biāo)和準(zhǔn)則：復(fù)雜性最低 算法復(fù)雜度分析 ? 和算法執(zhí)行時間相關(guān)的因素 ? 算法選用的策略 ? 問題的規(guī)模 ? 編寫程序的語言 ? 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 ? 計(jì)算機(jī)執(zhí)行指令的速度 算法復(fù)雜度分析 ? 問題的輸入規(guī)模（ Input Size）依賴于所研究的問題本身 ，輸入規(guī)模即為輸入項(xiàng)的個數(shù)，例如：排序和計(jì)算離散傅立葉變換（ DFT），輸入數(shù)組的元素個數(shù) n即為 input size 2. 還有一些問題，輸入規(guī)模表示輸入數(shù)據(jù)的二進(jìn)制形式的 bit位數(shù)，例如：兩個整型數(shù)據(jù)的乘法 3. 有時，輸入規(guī)模用兩個數(shù)表示，例如輸入是一個 圖 所以，解決問題之前先弄清 問題的輸入規(guī)模 后面均將輸入規(guī)模抽象成 n，算法的運(yùn)行時間表示成 T(n),n的函數(shù) 算法復(fù)雜度分析 ? 最好運(yùn)行時間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最快情況的運(yùn)行時間。運(yùn)行時間的下界 ? 最壞運(yùn)行時間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最慢或運(yùn)行步數(shù)最多時的運(yùn)行時間。 運(yùn)行時間的上界 ? 平均運(yùn)行時間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，平均所需的運(yùn)行時間，通常指概率平均或期望值 ? 運(yùn)行時間 T(n)：主要操作的執(zhí)行次數(shù) ? 非遞歸算法： （ 1） for / while 循環(huán) 循環(huán)體內(nèi)運(yùn)行時間 *循環(huán)次數(shù)； （ 2）嵌套循環(huán) 循環(huán)體內(nèi)運(yùn)行時間 *所有循環(huán)次數(shù)； （ 3）順序語句 各語句運(yùn)行時間相加； （ 4） ifelse語句 if語句運(yùn)行時間和 else語句運(yùn)行時間的較大者。 算法復(fù)雜度分析 算法分析舉例： InsertionSort
公司管理相關(guān)推薦
鄂ICP備17016276號-1