專升本計算機導(dǎo)論ppt課件(完整版)
【正文】 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 從邏輯關(guān)系上描述數(shù)據(jù) ， 與數(shù)據(jù)的存儲無關(guān) ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是 從具體問題抽象出來的數(shù)據(jù)模型 ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān) ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出數(shù)據(jù)都通過參數(shù)表顯式地傳遞，少用變量或全局變量，每個算法只完成一個功能。一個完整的算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。 ? I 輸入函數(shù) ? C 算法復(fù)雜性 , 應(yīng)表示為 C(n, I)。 26 算法復(fù)雜性的度量 (事例 ) ? 例 : 設(shè)變量 a、 b、 c、 d中各含一個整數(shù)。 if (cx) x=c。最壞情況下的時間復(fù)雜性分別為 5和 3。k++) C[i][j]=A[i][k]*B[k][j]。 ? 例子： ? 因為當(dāng) n≥1 時，有 3n ≤ 4n，則 有 3n=O(n)。 ? 2. O(f)+O(g)=O(f+ g)。 下界的階越高算法復(fù)雜評估的越準(zhǔn)確 。 ? 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。 False, True ? Boolean, +、 、 、 ==、 =等都是可用的服務(wù)。 40 抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types) ?為什么要引入抽象數(shù)據(jù)類型 按照頂向下逐步求精的原則 , 在探索運算步驟時 ,首先應(yīng)考慮算法的頂層運算步驟 , 然后再考慮底層運算步驟 . 頂層運算步驟 : 指定義在數(shù)據(jù)模型上的運算步驟 。 Ω常與 O配合以證明某問題的一個特定算法是該問題的最優(yōu)算法或該問題的某算法類中的最優(yōu)算法。 ? 4. 如果 g(n)=O(f(n)), O(f)+O(g)=O(f)。 ? 32 算法復(fù)雜性的漸近性態(tài) ? 例子： ? 因為當(dāng) n≥10 時，有 2n2+11n10 ≤3 n2 ，則 有 2n2+11n10 =O(n2)。通常， 當(dāng) n單調(diào)增加且趨于 ∞ 時， T（ n）也單調(diào)增加且趨于 ∞ 。in。 if (ab) x=a。 算法 max1: void max1(int a, b, c, d) { int x。 對于給定的算法 A，用到的元運算 Oi的次數(shù)為 ei, i=1,2, ? 設(shè)抽象的計算機所提供的元運算有 k種，分別記為 O1， O2， ? 時間復(fù)雜性： 需要的時間資源的量。這是理解、測試和修改算法的需要。 ? 順序存儲表示 ? 鏈接存儲表示 ? 索引存儲表示 ? 散列存儲表示 15 算法的概念 ? 算法的 定義： 由若干條指令組成的一個有窮序列 ，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列 ? 特性： ? 輸入 有 0個或多個輸入 ? 輸出 有一個或多個輸出 (處理結(jié)果 ) ? 確定性 每步定義都是確切、無歧義的 ? 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 16 程序與算法的區(qū)別 ? 程序可以不滿足有窮性。 數(shù)據(jù)項 是 具有獨立含義的最小標(biāo)識單位 。 ? 一個數(shù)據(jù)元素可以由若干 數(shù)據(jù)項(Data Item)組成。 10 數(shù)據(jù)的邏輯結(jié)構(gòu)分類 ? 線性結(jié)構(gòu) ? 線性表 ? 非線性結(jié)構(gòu) ? 多維數(shù)組 ? 廣義表 ? 樹 ? 圖（或網(wǎng)絡(luò)） 11 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 樹 二叉樹 二叉搜索樹 14 13 12 11 2 3 4 5 6 7 8 9 10 3 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1