前言：數據結構與算法作為計算機經典的基礎理論課程，同時作為計算機類專業考研課程，並且在校招面試時常被提及，其重要性可見一斑。除此之外，學習這門課程有助於我們用編程去解決、思考問題，設計出更簡潔、效率更高的代碼。
一.課程概述
-
數據結構課程研究什麼？
- 內存中基本數據組織和數據處理的方法
- 非數值問題
-
通過學習數據結構獲得什麼？
- 經典數據結構和經典算法的基本原理
-
學習重點
- 數據結構的邏輯特性和存儲結構設計
- 數據結構算法設計基本方法和分析方法
- 利用數據結構解決實際問題
二.基本概念與術語
-
數據
- 能輸入到計算機中，被程序識別和處理的一切事物的符號化表示
-
數據元素
- 數據的基本單位
-
數據項
- 構成數據元素的最小單位
-
存儲結構（由想法到算法）
- 順序存儲結構
- 鏈式存儲結構
-
邏輯結構（由問題到想法）
- 一種邏輯結構可由多種存儲結構實現
-
數據結構
- 邏輯結構
- 存儲結構
- 數據運算
-
抽象數據類型（ADT）
ADT 抽象數據類型名{ 數據對象的定義 數據元素之間的邏輯關係定義 基本運算定義 }ADT -
算法的定義
- 基於存儲結構的運算實現的步驟
- 滿足有窮性、確定性、可行性
- 有0個或多個輸入，1個或多個輸出
-
什麼是好的算法
- 正確性：對於合法輸入，算法能得出正確結果
- 健壯性：對於非法輸入，算法能做出特別處理
- 可理解性：算法容易理解、實現
- 高效性：具有較短執行時間並佔用較少空間
- 可修改、可拓展性
三.算法分析
-
時間複雜度
- 是算法求解問題規模n的函數，T(n)=F(n)，F(n)是基本語句的執行頻度
- 增長率：忽略低次冪和最高次冪係數
-
分析規則
- 加法規則：針對並列程序段
- 乘法規則：針對嵌套程序段
-
例子
++x; //複雜度O(1) for(i=1;i<=n;++i) ++x; //複雜度O(n) for(i=1;i<=n;++i) for(j=1;j<=n;++j) ++x; //複雜度O(n²) -
常見的時間複雜度
O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!) -
空間複雜度
- 除去輸入輸出佔用空間，算法臨時佔用的存儲空間
- S(n)=O(f(n))
完整內容可以訪問我的個人博客：數據結構 515code.com