目錄

• 一、數據結構
• • 1、什么是數據結構
  • 2、什么是算法
  • 3、數據結構和算法的重要性
  • 4、如何學好數據結構和算法
• 二、算法效率
• 三、時間復雜度
• • 1、時間復雜度的概念
  • 2、時間復雜度的表示方法
  • 3、算法復雜度的三種情況
  • 4、簡單時間復雜度的計算
  • 5、復雜時間復雜度的計算
  • 五、不同時間復雜度效率的比較
• 四、空間復雜度
• • 1、空間復雜度的概念
  • 2、空間復雜度的計算方法
  • 3、常見空間復雜度的計算
• 五、總結

一、數據結構

1、什么是數據結構

數據結構(Data Structure)是計算機存儲、組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合。簡單來說，數據結構就是對數據進行管理（增刪查改）的一系列操作。

數據結構和數據庫的作用很相似，二者的區別在于管理的位置不同：當數據量很大時，數據一般都會存放在磁盤中，此時我們用數據庫進行管理；當數據量相對較小時，我們用數據結構來管理。

2、什么是算法

算法 (Algorithm) 就是定義良好的計算過程，他取一個或一組的值為輸入，并產生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

數據結構和算法是相輔相成的，二者是我中有你、你中有我的關系：在一個數據結構中可能會用到算法來優化，一個算法中也可能用到數據結構來組織數據。

3、數據結構和算法的重要性

在校園招聘的筆試：

目前校園招聘筆試一般采用Online Judge (在線OJ) 形式， 一般都是20-30道選擇題+2道編程題，或者3-4道 編程題。

可以看出，現在公司對我們代碼能力的要求是越來越高了，大廠筆試中幾乎全是算法題而且難度大，中小廠的筆試中才會有選擇題。算法不僅筆試中考察，面試中面試官基本都會讓現場寫代碼。而算法能力短期內無法快速提高，至少需要持續半年以上算法訓練積累，否則真正校招時 試會很艱難，因此算法要早早準備。

在校園招聘的面試中：

在面試環節，數據結構和算法也是被經常問到的一部分，大家在?？?、LeetCode的面經中也能夠發現這一點，比如如下的一些問題：

• 怎么用兩個棧實現一個隊列？
• 如何判斷兩個鏈表是否相交？
• Vector和數組的區別？
• 紅黑樹的原理、時間復雜度等？
• map和set底層原理？
• 快速排序思想是什么？
• Hashmap的原理？

在未來的工作中：

這里我引用網上的一篇文章：學好算法對一個程序員來說是必須的嗎？如果是，至少應該學到哪種程度

4、如何學好數據結構和算法

關于這個問題的答案，我想大家都知道，要想學好數據結構和算法，除了多練還是多練，至少我們需要把《劍指offer》《程序員代碼面試指南》全部刷完，LeetCode至少刷幾百道題，然后就是注意在做具體題目之前要先畫圖分析，理清思路之后再下手。

劍指offer 程序員面試經典 LeetCode OJ 題庫

---

二、算法效率

算法的復雜度

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度。

時間復雜度主要衡量的是一個算法的運行速度，而空間復雜度主要衡量一個算法所需要的額外空間。

在計算機發展的早期，計算機的存儲容量很小，所以對空間復雜度很是在乎；但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度；所以我們如今已經不需要再特別關注一個算法的空間復雜度，而更注重于時間復雜度。

算法復雜度在校招中的考察

---

三、時間復雜度

1、時間復雜度的概念

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。(這里的函數指的是數學中的函數，而不是我們C語言中的函數)

一個算法執行所耗費的時間，從理論上說是不能算出來的，因為只有當我們把程序放在機器上跑起來，才能知道具體時間。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。

一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間復雜度。

2、時間復雜度的表示方法

我們計算時間復雜度時不是計算算法運行的具體次數，而是用大O的漸進表示法來計算，其具體計算方法如下：

• 用常數1取代運行時間中的所有加法常數。
• 在修改后的運行次數函數中，只保留最高階項。
• 如果最高階項存在且不是1，則去除與這個項目相乘的常數。

3、算法復雜度的三種情況

算法的復雜度分為三種情況：

• 最壞情況：任意輸入規模的最大運行次數(上界)
• 平均情況：任意輸入規模的期望運行次數
• 最好情況：任意輸入規模的最小運行次數(下界)

例如：在一個長度為N數組中搜索一個數據x

最好情況：1次找到
平均情況：N/2次找到
最壞情況：N次找到
平均情況：N/2次找到

在實際中一般情況關注的是算法的最壞運行情況，所以數組中搜索數據時間復雜度為O(N)。

4、簡單時間復雜度的計算

例1：

void Func(int N) { int count = 0; for (int k = 0; k < 100; ++ k) {++count; } printf("%d\n", count); }

上面程序具體執行的次數：100

用大O的漸進表示法得出時間復雜度：O(1) (用常數1取代運行時間中的所有加法常數。)

例2：

void Func1(int N) {int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count); }

上面程序具體執行的次數：N * N + 2*N + 10

用大O的漸進表示法得出時間復雜度：O(N^2) (只保留最高階項)

例3：

void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k) {++count; } int M = 10; while (M--) {++count; } printf("%d\n", count); }

上面程序具體執行的次數：2*N + 10

用大O的漸進表示法得出時間復雜度：O(N) (如果最高階項存在且不是1，則去除與這個項目相乘的常數

5、復雜時間復雜度的計算

（1）冒泡排序的時間復雜度

void BubbleSort(int arr[], int n) {int i = 0;int j = 0;for (i = 0; i < n - 1; i++){for (j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}} }

具體執行次數：時間復雜度計算時以最壞情況為準，則假設數組開始是逆序的，那么第一次排序執行 n-1 次，第二次排序執行 n-2 次，第三次執行 n-3 次 … …，直到最后達成有序，所以冒泡排序的具體執行次數是一個等差數列，具體次數 = (首項+尾項)/2*項數 = (N^2-N)/2

用大O的漸進表示法得出時間復雜度：O(N^2)

（2）二分查找的時間復雜度

int BinarySearch(int arr[], int n, int x) //n元素個數 x:要查找的數 {int left = 0;int right = n - 1;while (left < right){int mid = (left + right) / 2;if (arr[mid] > x){right = mid - 1; //中間元素比x大就挪動right下標}else if (arr[mid] < x){left = mid + 1; //中間元素比x小就挪動left下標}elsereturn mid; //找到就返回該元素所在的下標}return 0; //找不到就返回0 }

具體執行次數：和上面一樣，這里考慮最壞情況，即數組中沒有想找的元素，數組會從中間開始查找，每次排除掉一半的元素，直到把所有元素排除完，第一次排除后剩下 1/2 的元素，第二次排除后剩下 1/4 元素，第三次排除后剩下 1/8 元素 … …，設元素個數為N，查找次數為X，則 X * (?)^N = 1 -> (?)^N = X -> 具體次數：X = log₂N

用大O的漸進表示法得出時間復雜度：O(logN)

注：因為在鍵盤上無法表示出log的底數，所有在時間復雜度中把log的底數2省略掉了，直接用logN表示log₂N的時間復雜度。

（3）階乘遞歸的時間復雜度

long long Factorial(int N) {return N < 2 ? N : Factorial(N - 1) * N; }

具體次數：這里 n 調用 n-1 , n-1 調用 n-2 …，直到 n = 1，所以一共執行了 n-1 次。

用大O的漸進表示法得出時間復雜度：O(N)

以五的階乘示例：

（4）斐波那契遞歸的時間復雜度

long long Fibonacci(size_t N) {return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2); }

具體次數：以上圖為例，我們可以看到在數值大于2的時候，每一層的調用次數是以2的指數形式增長的，是一個等比數列。

用大O的漸進表示法得出時間復雜度為：O(2^N)

五、不同時間復雜度效率的比較

我們可以看到當測試數據很大時 O(logN) 和 O(1) 的效率幾乎是一樣的，所以二分查找是一種效率很高的算法，但是它也有一個缺陷，那就是它操作的數組元素必須是有序的。

---

四、空間復雜度

1、空間復雜度的概念

空間復雜度也是一個數學表達式，是對一個算法在運行過程中額外占用存儲空間大小的量度 。

空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，空間復雜度算的是變量的個數。 空間復雜度計算規則基本跟時間復雜度類似，也使用大O的漸進表示法。

注意：函數運行時所需要的?？臻g(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

2、空間復雜度的計算方法

空間復雜度的計算方法和時間復雜度非常相似，且都是用大O的漸進表示法表示。 具體計算方法如下：

• 用常數1取代運行過程中定義的常數個變量。
• 在修改后的運行次數函數中，只保留最高階項。
• 如果最高階項存在且不是1，則去除與這個項目相乘的常數。

3、常見空間復雜度的計算

（1）冒泡排序的空間復雜度

void BubbleSort(int arr[], int n) {int i = 0;int j = 0;for (i = 0; i < n - 1; i++){for (j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}} }

這里我們在循環外部定義了兩個變量，然后在循環內部又定義了一個變量；可能有的同學會認為temp變量因為在循環內部，每次進入循環都會被重新定義，所以空間復雜度為N^2，其實不是的；

我們知道雖然時間是累積的，一去不復返，但是空間是不累積的，我們可以重復使用；對于我們的temp變量來說，每次進入if這個局部范圍時開辟空間，離開這個局部范圍時空間銷毀，下一次在進入時又重新開辟空間，出去又再次銷毀；所以其實從始至終temp都只占用了一個空間；

所以上面一共一共定義了三個變量，用大O的漸進表示法得到空間復雜度為O(1)。

（2）二分查找的空間復雜度

int BinarySearch(int arr[], int n, int x) //n元素個數 x:要查找的數 {int left = 0;int right = n - 1;while (left < right){int mid = (left + right) / 2;if (arr[mid] > x){right = mid - 1; //中間元素比x大就挪動right下標}else if (arr[mid] < x){left = mid + 1; //中間元素比x小就挪動left下標}elsereturn mid; //找到就返回該元素所在的下標}return 0; //找不到就返回0 }

和冒泡排序的空間復雜度一樣，這里只定義了三個（常數個）變量，所以空間復雜度是O(1)。

（3）階乘遞歸的空間復雜度

long long Fac(int N) {return N < 2 ? N : Factorial(N - 1) * N; }

我們知道，每次函數調用開始時都會在棧區上形成自己的函數棧幀，調用結束時函數棧幀銷毀；

對于上面的遞歸來說：只有當 N < 2 的時候函數才開始返回，而在這之前所形成的 Fac(N) Fac(N-1) Fac(N-2) … 這些函數的函數棧幀在返回之前都不會釋放，而是一直存在，知道函數一步一步開始返回的時候開辟的空間才會被逐漸釋放。所以在計算遞歸類空間復雜度度時，我們在意的是遞歸的深度；

這里調用的遞歸深度為 n - 1（遞歸 n - 1 次），所以空間復雜度為O(N)。

（4）斐波那契遞歸的空間復雜度

long long Fibonacci(size_t N) {return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2); }

首先就，斐波那契是逐個分支進行遞歸的，以上圖為例，它會先遞歸6-5-4-3-2-1，再遞歸6-5-4-3-2，再遞歸6-5-4-2，以此類推，直到把最后一個分支遞歸完；

其次，空間是不會累積的，所以盡管我們同一個函數的函數棧幀會被開辟很多次，但是它仍然只計入一次開辟的空間復雜度。

所以遞歸調用開遞歸的深度，這里的空間復雜度為O(N)。

五、總結

• 時間復雜度和空間復雜度都是用大O的漸進表示法來表示。
• 時間復雜度看運算執行的次數，空間復雜度看變量定義的個數。
• 在遞歸中，時間復雜度看調用的次數，空間復雜度看調用的深度。
• 時間是累積的，一去不復返；空間是不累積的，可以重復利用。

• 冒泡排序的時間復雜度為O(N^2)，空間復雜度為O(1)。
• 二分查找的時間復雜度為O(logN)，空間復雜度為O(1)。
• 階乘遞歸的時間復雜度為O(N)，空間復雜度為O(N)。
• 斐波那契遞歸的時間復雜度為O(2^N)，空間復雜度為O(N)。

---

總結

以上是生活随笔為你收集整理的【数据结构】时间复杂度和空间复杂度的计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。