C語言【數據結構】：時間復雜度和空間復雜度.詳解

引言

? ? ? ? 詳細介紹什么是時間復雜度和空間復雜度。

前言：為什么要學習時間復雜度和空間復雜度

????????算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。

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

一、時間復雜度?

問：時間復雜度是程序運行的時間嗎？? ? ? ? ? ? ? ? ? ? ?

????????這是一個很嚴重的問題。這里先肯定回答：不是。

仔細往下看，最后你親自來回答這個問題?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1.什么是時間復雜度

????????時間復雜度是對一個算法運行時間長短的一種度量，它描述的是隨著輸入數據規模?n?的增大，算法執行時間的增長趨勢，而不是具體的運行時間。因為具體運行時間會受到硬件、編程語言、編譯器等多種因素的影響，所以使用時間復雜度可以更客觀地評估算法的效率。

? ??

程序執行的時間? =? 二進制指令運行的時間 * 執行的次數?

????????因為程序在計算機中二進制指令的運行時間是非常快的，可以假定時間是一樣的，所以使用代碼的執行次數來等效程序的執行時間?

2.表示方法（大O表示法）

????????通常使用大 O 符號（Big O notation）來表示時間復雜度。大 O 符號表示的是算法執行時間的上界，即最壞情況下的時間復雜度。看到這里你可能不知道什么是大O表示法，跟隨下面的案例來理解，就明白什么是大O表示法了。

????????推導大O階規則

????????1. 時間復雜度函數式 T(N) 中，只保留最高階項，去掉那些低階項，因為當 N 不斷變?時，低階項對結果影響越來越?，當 N 無窮大時，就可以忽略不計了。

???????? 2. 如果最高階項存在且不是 1 ，則去除這個項目的常數系數，因為當 N 不斷變大，這個系數對結果影響越來越小，當 N 無窮大時，就可以忽略不計了。

???????? 3.T(N) 中如果沒有 N 相關的項目，只有常數項，用常數 1 取代所有加法常數。

3.常見的時間復雜度

1.?O(1)：常數時間復雜度

代碼一：

? ? ? ? 推導一下這段代碼的執行次數T與n之間的函數關系


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);
}

? ? ? ? T（N）= 2 * N + 10；

當N足夠大時，從1 增長到10000000，會發現2 和10 對次數的影響不是很大，所以

? ? ? ? 1. 如果最高階項存在且不是 1 ，則去除這個項目的常數系數，因為當 N 不斷變大，這個系數對結果影響越來越小，當 N 無窮大時，就可以忽略不計了。

? ? ? ? 2.?T(N) 中如果沒有 N 相關的項目，只有常數項，用常數 1 取代所有加法常數。

代碼二：?


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

????????觀察這段代碼，會發現n和程序的執行次數是沒有關系的（T（N）= 100），這時就認為時間復雜度為O（1）；

2.?O(n)：線性時間復雜度

代碼一：

????????算法的執行時間與輸入數據規模?n?成正比。

#include <stdio.h>// 計算數組元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

????????在?sum?函數中，需要遍歷數組中的每個元素，因此循環的執行次數與數組的長度?n?成正比，時間復雜度為?O(n)。即因為是要循環n次，所以是O(n)。

代碼二：?


const char* strchr(const char* str, int character)
{const char* p_begin = 's';while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;

?strchr執行的基本操作次數：

1）若要查找的字符在字符串第?個位置，則： T(N) = 1

2）若要查找的字符在字符串最后的?個位置，則： T(N) = N

3）若要查找的字符在字符串中間位置，則：N T(N) = 2 因此：strchr的時間復雜度分為：最好情況： O(1)

最壞情況： O(N)

平均情況： O(N)

通過上面我們會發現，有些算法的時間復雜度存在最好、平均和最壞情況。

最壞情況：任意輸入規模的最大運行次數(上界)

平均情況：任意輸入規模的期望運行次數

最好情況：任意輸入規模的最小運行次數(下界)

大O的漸進表示法在實際中?般情況關注的是算法的上界，也就是最壞運行情況。

所以上面這段代碼的時間復雜度是O（N）

3.?O(n^2)：平方時間復雜度

????????算法的執行時間與輸入數據規模?n?的平方成正比。

參考代碼：

#include <stdio.h>// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int 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;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

粗略理解：在?bubbleSort?函數中，使用了兩層嵌套循環，因此時間復雜度為?O(n^2)。

細節分析：

????????1）若數組有序，則： T(N)=N

? ? ? ? 2）若數組有序且為降序，則： T(N)=? 1 + 2 + 3 + .......+ n - 1 = ((n - 1)?* (1 + n - 1) ) / 2? ?即等差數列求和公式：a1 = 1， an = n - 1, 共n - 1項。

? ? ? ? T（N）= (n^2) * 1 / 2 + n / 2;

???????因此：BubbleSort的時間復雜度取最差情況為： O(N ^ 2)

4.?O(log n )：復雜度

參考代碼：

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

當n= 2?時，執行次數為1

當n= 4?時，執行次數為2

當n=16時，執行次數為4

假設執行次數為x，則 2^x?= x? 因此執行次數： x=logn

因此：func5的時間復雜度取最差情況為：O(log?n)?

這里為什么不寫

因為這個在輸入法上不好打出來

注意：在有的地方會把? logn? 寫成lgn，嚴格上來說這個是不對的

????????當n接近無窮大時，底數的大小對結果影響不大。因此，一般情況下不管底數是多少都可以省略不寫。

還有其他的時間復雜度如：n*logn, n!(n的階乘)，在以后的學習中肯定會遇到

二、空間復雜度

?1.什么是空間復雜度

定義

????????空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的一種度量，它描述的是隨著輸入數據規模?n?的增大，算法所需額外存儲空間的增長趨勢。

注意：函數棧幀的創建和銷毀是不算入空間復雜度的，即創建函數和銷毀函數是不算入時間復雜度的。

表示方法

????????同樣使用大 O 符號來表示空間復雜度。

常見的空間復雜度及其示例代碼

1.?O(1)：常數空間復雜度

算法在運行過程中所需的額外存儲空間是固定的，不隨輸入數據規模?n?的變化而變化。

#include <stdio.h>// 計算數組元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

????????在 sum 函數中，只使用了一個額外的變量?total?來存儲數組元素的和，因此空間復雜度為?O(1)。

2.?O(n)：線性空間復雜度

算法在運行過程中所需的額外存儲空間與輸入數據規模?n?成正比。

#include <stdio.h>
#include <stdlib.h>// 復制數組
int* copyArray(int arr[], int n) {int *newArr = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {newArr[i] = arr[i];}return newArr;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int *newArr = copyArray(arr, n);for (int i = 0; i < n; i++) {printf("%d ", newArr[i]);}printf("\n");free(newArr);return 0;
}

在copyArray 函數中，使用了 malloc 函數動態分配了一個大小為?n?的數組，因此空間復雜度為?O(n)。?

5. 常見復雜度對比

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

? ? ? ? 但是，在算法競賽中，往往需要有一種思想：用時間換空間，或者用空間換時間。