第一章 緒論
- 1.1資料結構的基本概念
- 1.2算法和算法評價
重點：算法的時間複雜度
1.1資料結構的基本概念
1.資料結構包括：邏輯結構、存儲結構、資料的運算。
2.邏輯結構：是指資料元素之間的邏輯關系，與資料存儲無關（集合、線性結構、樹形結構、圖狀結構或網狀結構）。
3.存儲結構：實體結構，是用計算機語言實作的邏輯結構（順序存儲、鍊式存儲、索引存儲、散列存儲）。
4.順序存儲可以随機存取，鍊式存儲隻能順序存取。
5.邏輯結構獨立于存儲結構。
6.可以用抽象資料類型定義一個完整的資料結構。
7.有序表屬于邏輯結構，描述元素間的邏輯關系，既可鍊式存儲，又可順序存儲。
8.棧與存儲結構無關，是一種抽象資料類型，可采用順序或鍊式存儲，隻表示邏輯結構。
9.循環隊列是用順序表表示的。
1.2算法和算法評價
1.算法：（有窮性、确定性、可行性、輸入、輸出）。
時間複雜度：O(n)
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
2.空間複雜度：S(n)，是問題規模n的函數。
3.嚴蔚敏書原話：同一個算法，實作語言的級别越高，執行效率越低。
完結