1. 資料
- 資料：資料是指對客觀事物進行記錄并且可以可以鑒別的抽象符號
- 資料元素：資料的基本單位，在計算機當中作為一個整體考慮
- 資料物件：具有相同性質的資料元素的集合
- 資料結構：計算機儲存、組織資料的方式
2. 結構
- 邏輯結構：直接面向問題
- 集合
- 線性結構
- 樹狀結構
- 圖結構
- 物理結構：面向計算機，資料元素的值+邏輯結構
- 連續設計：通過資料之間的相對位置來表示資料元素之間的邏輯關系
- 鏈接設計：通過存放的指標\(Pointer\)
- 邏輯結構和物理結構的區別和聯系
- 區別：邏輯結構面向問題，物理結構面向計算機
- 聯系：物理結構是面向計算機的具體的邏輯結構
3. 資料結構的運算
- 資料結構的組成部分
- 邏輯結構：\(D\_S = (D , S)\)
- 存盤結構
- 資料操作
- 資料結構的運算
- 會改變資料結構的運算操作
- 建立\((Create)\)一個資料結構
- 銷毀\((Destroy)\)一個資料結構
- 從一個資料結構中洗掉\((Delete)\)一個資料元素
- 從一個資料結構中插入\((Insert)\)一個資料元素
- 不會改變資料結構本身的運算操作
- 對一個資料結構進行訪問\((Access)\)
- 對一個資料結構中的元素進行修改\((Modify)\)
- 對資料結構中的所有元素進行排序\((Sort)\)
- 對一個資料結構進行查找\((Search)\)
- 會改變資料結構的運算操作
4. 資料型別
- 資料型別：資料的取值范圍 \(+\) 一系列操作
- 抽象資料型別\((ADT)\)：為了解決特定問題而定義的資料型別
- 二者的聯系：資料型別是已定義好的抽象資料型別，抽象資料型別由資料型別組成
5. 演算法
- 演算法的概念：對特定問題求解方法的一種描述，是指令的有限序列
- 演算法的特性
- 確定性：不能有二義性
- 可行性
- 輸入/ 輸出
- 有限性：一個演算法總是在經歷了有窮步的運算之后會終止
- 演算法的描述方法
- 自然語言：用序號表示，避免自然段！
- 流程圖
- 偽代碼\((Pseudocode)\)
- 直接代碼
- 評價演算法的標準
- 正確性、可讀性、通用性
- 健壯性\((Robustness)\)：有容錯處理
- 效率與存盤量需求：時間復雜度和空間復雜度
- 演算法效率的分析
- 時間復雜度
- \(\exists c>0,n>n_0,f(n) < cg(n)\)，則\(f(n) = O (g(n))\)
- \(\exists c>0,n>n_0,f(n) > cg(n)\), 則\(f(n) = \Omega(g(n))\)
- \(f(n) = O (g(n)) , f(n) = \Omega(g(n))\)，則\(f(n) = \Theta(g(n))\)
- 常用的時間復雜度：\(O (1)<O (\log n)<O (n)<O (n\log n)<O (n^2)<O (n^3)<O (2^n)<O (n!)<O (n^n)\)
- 簡單的運演算法則：
- \(O (f)+O (g) = O (max(f,g))\)
- \(O (f)\cdot O (g) = O (f*g)\)
- \(O (cf(n)) = O (f(n))\)
- 空間復雜度
- 時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510916.html
標籤：其他
上一篇：網路層：資料平面