前言:數據結構與算法作為計算機經典的基礎理論課程,同時作為計算機類專業考研課程,並且在校招面試時常被提及,其重要性可見一斑。除此之外,學習這門課程有助於我們用編程去解決、思考問題,設計出更簡潔、效率更高的代碼。
一.課程概述
-
數據結構課程研究什麼?
- 內存中基本數據組織和數據處理的方法
- 非數值問題
-
通過學習數據結構獲得什麼?
- 經典數據結構和經典算法的基本原理
-
學習重點
- 數據結構的邏輯特性和存儲結構設計
- 數據結構算法設計基本方法和分析方法
- 利用數據結構解決實際問題
二.基本概念與術語
-
數據
- 能輸入到計算機中,被程序識別和處理的一切事物的符號化表示
-
數據元素
- 數據的基本單位
-
數據項
- 構成數據元素的最小單位
-
存儲結構(由想法到算法)
- 順序存儲結構
- 鏈式存儲結構
-
邏輯結構(由問題到想法)
- 一種邏輯結構可由多種存儲結構實現
-
數據結構
- 邏輯結構
- 存儲結構
- 數據運算
-
抽象數據類型(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