| 編者幾憾訓每天抽一點點時間，慢慢更新這個檔案，也歡迎大家留言補充， |
快速導航
- 滿二叉樹的結點
- 演算法空間復雜度 / 有窮性
- 線性結構
- 中序遍歷
- 后序遍歷
- 演算法基本特征
- 希爾排序法（插入類排序）
- 演算法是啥
- 幾個排序方法
- 順序存盤結構 / 鏈式存盤結構
- 在單鏈表中，增加頭結點的目的
- 演算法分析的目的
- 強連通圖
- 線性表——堆疊
- 基本排序演算法的比較次數
- 邏輯結構——存盤結構——效率
- 線性結構 / 非線性結構
滿二叉樹的結點
- 某層的：第K層—— 2 k ? 1 2^{k-1} 2k?1
- 總共的：深度為m—— 2 m 2^{m} 2m
- 滿二叉樹中，最后一層的結點個數就是葉子結點的個數
演算法空間復雜度 / 有窮性
- 演算法的空間復雜度：演算法在運行程序中需輔助存盤空間的大小，
- 演算法的有窮性：一個演算法必須在執行有限的步驟以后結束，
線性結構
線性表、堆疊和佇列等資料結構所表達和處理的資料以線性結構為組織形式，
- 堆疊又稱后進先出表
- 佇列又稱先進先出表
中序遍歷
- “左根右”
首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹;
并且在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹，
- 例題：
答案是：DBEAFC
后序遍歷
- “左右根”
首先遍歷左子樹，然后訪問右子樹，最后遍歷根結點;
并且遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，
- 例題：
答案是：DEBFCA
演算法基本特征
1、可行性
2、確定性
3、有窮性
4、擁有足夠的情報
希爾排序法（插入類排序）
- 希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序，所以希爾排序法屬于插入類排序
演算法是啥
- 是解題方案的準確而完整的描述
幾個排序方法
- 快速排序的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄繼續進行排序，以達到整個序列有序;
- 插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中，從而得到一個新的序列;
- 選擇排序的基本思想是:掃描整個線性表，從中選出最小的元素，將它交換到表的最前面(這是它應有的位置），然后對剩下的子表采用同樣的方法，直到表空為止;
- 歸并排序是將兩個或兩個以上的有序表組合成一個新的有序表，
- 以上幾個排序方法中，要求記憶體量最大的是歸并排序，
順序存盤結構 / 鏈式存盤結構
- 順序存盤結構中，資料元素存放在一組地址連續的存盤單元中，每個資料元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到，從而實作了隨機存取，
- 鏈式存盤結構，要對某結點進行存取，都得從鏈的頭指標指向的結點開始，這是一種順序存取的存盤結構，
在單鏈表中，增加頭結點的目的
頭結點不僅標識表中首結點的位置，而且根據單鏈表（包含頭結點)的結構，只要掌握表頭，就能夠訪問整個鏈表，因此增加頭結點目的是為了便于運算的實作，
演算法分析的目的
- 演算法分析是指對一個演算法的運行時間和占用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示，
- 分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度，提高演算法的執行效率，簡單的說就是分析演算法效率以求改進，
強連通圖
在有向圖中，若任意兩個頂點都連通，則稱該圖是強連通圖，這樣的有向圖的形狀是環狀，因而至少應有n條邊，
線性表——堆疊
- 線性表可以順序存盤，也可以鏈式存盤，而堆疊是一種線性表，也可以采用鏈式存盤結構，
- 堆疊是后進先出表，當然堆疊是有記憶作用的，
基本排序演算法的比較次數
假設線性表的長度為n，則在最壞情況下:
- 冒泡排序需要經過n/2遍的從前往后掃描和n/2遍的從后往前掃描，需要比較次數為n(n-1)/2
- 快速排序法的最壞情況比較次數也是n(n-1)/2
邏輯結構——存盤結構——效率
- 一種資料的邏輯結構根據需要可以表示成多種存盤結構，
- 常用的存盤結構有順序、鏈接、索引等存盤結構，
- 采用不同的存盤結構，其資料處理的效率是不同的，
所以一個邏輯資料結構可以有多種存盤結構，且各種存盤結構影響資料處理的效率，
線性結構 / 非線性結構
-
根據各資料元素之間前后關系的復雜程度，一般將資料結構分為兩大型別:線性結構與非線性結構，
-
如果一個非空的資料結構滿足下列兩個條件,則稱該資料結構為線性結構，又稱線性表.
- 有且只有一個根結點;
- 每個結點最多有一個前件，也最多有一個后件，
-
線性表、堆疊與佇列、線性鏈表都是線性結構，而二又樹是非線性結構
| 看完點個贊唄，速評一下更有動力哦 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348382.html
標籤：其他
下一篇：程式與邏輯演算法學習03