前言

數據結構_空間復雜度_時間復雜度講解_常見復雜度對比

本文介紹數據結構中的時間復雜度和空間復雜度
***文章末尾，博主進行了概要總結，可以直接看總結部分***

博主博客鏈接：https://blog.csdn.net/m0_74014525
點點關注，后期持續更新系列文章

文章目錄

前言
一、算法效率
二、時間復雜度
- 1. 時間復雜度的定義
- 2. 大O的漸進表示法
- 3. 時間復雜度計算舉例
三、空間復雜度
- 1. 空間復雜度的定義
- 2. 空間復雜度計算舉例
四、常見復雜度對比
- 1. 常見的時間復雜度及其對應的算法
- 2. 常見復雜度的對比
總結

一、算法效率

算法效率指的是算法在處理數據時所消耗的時間和空間資源的多少。

算法效率通常由時間復雜度和空間復雜度來衡量。

時間復雜度： 表示算法在處理數據時所需要的運算次數與數據規模之間的關系。

空間復雜度： 表示算法在處理數據時所需要的存儲空間與數據規模之間的關系。

算法效率的好壞直接影響到算法的執行速度和資源利用率，是算法設計時需要考慮的重要因素之一。

二、時間復雜度

1. 時間復雜度的定義

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。

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

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

即：找到某條基本語句與問題規模N之間的數學表達式，就是算出了該算法的時間復雜度。

舉例說明：

// 請計算一下Func1中++count語句總共執行了多少次？
void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){									//外層循環n次for (int j = 0; j < N; ++j){++count;					//內層循環n次//n*n}}for (int k = 0; k < 2 * N; ++k){++count;					//2*N 次}int M = 10;while (M--){++count;					//循環10次}printf("%d\n", count);
}

Func1 執行的基本操作次數：

$F(N)=N^2+2*N+10$
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法。

使用大O的漸進表示法以后，Func1的時間復雜度為：

$O(N^2)$

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。

2. 大O的漸進表示法

大O表示法是算法時間復雜度的漸進表示法，表示算法的運行時間在最壞情況下的漸進上限。

大O符號（Big O notation）：是用于描述函數漸進行為的數學符號。

推導大O階方法：
1、用常數1取代運行時間中的所有加法常數。
2、在修改后的運行次數函數中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。

有些算法的時間復雜度存在最好、平均和最壞情況：

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

在實際中一般情況關注的是算法的最壞運行情況
需要注意的是，大O表示法只關注算法的漸進時間復雜度，而不關注算法的具體實現細節和常數項。因此，兩個算法的時間復雜度可能相同，但它們的實際運行時間可能差別很大，這需要具體問題具體分析。

3. 時間復雜度計算舉例

實例1：

// 計算Func2的時間復雜度？
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);
}

實例1解析：
上述算法基本操作執行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)

實例2：

// 計算Func3的時間復雜度？
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

實例2解析：
上述算法基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)

實例3:

// 計算Func4的時間復雜度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

實例3解析：
上述算法基本操作執行了10次，通過推導大O階方法，時間復雜度為 O(1)

實例4:

// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );

實例4解析：
上述算法基本操作執行最好1次，最壞N次，時間復雜度一般看最壞，時間復雜度為 O(N)

實例5:

// 計算BubbleSort的時間復雜度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

實例5解析：
上述算法基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)

實例6:

// 計算BinarySearch的時間復雜度？
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左閉右閉區間，因此有=號while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

實例6解析：
上述算法基本操作執行最好1次，最壞O(logN)次，時間復雜度為 O(logN)
ps：logN在算法分析中表示是底數為2，對數為N。有些地方會寫成lgN。（建議通過折紙查找的方式講解logN是怎么計算出的）

實例7:

// 計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

實例7解析：
上述算法通過計算分析發現基本操作遞歸了N次，時間復雜度為O(N)。

實例8:

// 計算斐波那契遞歸Fib的時間復雜度？
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

實例8解析：
實例8通過計算分析發現基本操作遞歸了2^N次，時間復雜度為O(2^N)。

三、空間復雜度

1. 空間復雜度的定義

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

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

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

2. 空間復雜度計算舉例

實例1：

// 計算BubbleSort的空間復雜度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end)   		//end{int exchange = 0;           			//exchangefor (size_t i = 1; i < end; ++i)		//i   {if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

實例1解析：
上面算法里用三個變量，為常數個變量
使用了常數個額外空間，所以空間復雜度為 O(1)

實例2：

// 計算Fibonacci的空間復雜度？
// 返回斐波那契數列的前n項
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

實例2解析：
上面算法使用malloc動態內存函數開辟了N個空間
動態開辟了N個空間，空間復雜度為 O(N)

實例3：

// 計算階乘遞歸Fac的空間復雜度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

實例3解析：
上述算法使用了遞歸
遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O(N)

四、常見復雜度對比

1. 常見的時間復雜度及其對應的算法

大O漸進表示法	時間復雜度類型	算法的執行時間與輸入規模關系	對應算法
O(1)	常數時間復雜度	表示算法的執行時間與輸入規模無關	例如：訪問數組元素、哈希表操作等。
O(log n)	對數時間復雜度	表示算法的執行時間與輸入規模的對數相關	例如：二分查找、平衡二叉樹操作等。
O(n)	線性時間復雜度	表示算法的執行時間與輸入規模成線性關系	例如：線性查找、順序遍歷數組等。
O(n log n)	線性對數時間復雜度	表示算法的執行時間介于線性和對數之間	例如：歸并排序、快速排序等。
O(n^2)	平方時間復雜度	表示算法的執行時間與輸入規模的平方相關	例如：冒泡排序、選擇排序等。
O(n^3)	立方時間復雜度	表示算法的執行時間與輸入規模的立方相關	例如：矩陣乘法等。
O(2^n)	指數時間復雜度	表示算法的執行時間與輸入規模的指數相關	例如：求解子集、窮舉等。