C 語言數據結構（一）：時/空間復制度

一、前言

1. 什么是數據結構

2. 什么是算法

二、時 / 空間復雜度

1. 算法效率

2. 時間復雜度

2.1 時間復雜度的概念

2.2 大 O 的漸進表示法

2.3 常見的計算時間復雜度的例子

2.3.1 實例 1

2.3.2 實例 2

2.3.3 實例 3

2.3.4 實例 4

2.3.5 實例 5 ：冒泡排序

2.3.6 實例 6 ：二分查找

2.3.7 實例 7 ：階乘遞歸

2.3.8 實例 8 ：斐波那契遞歸

3. 空間復雜度

3.1?空間復雜度的概念

3.2 顯式申請的額外空間

3.3?常見的計算空間復雜度的例子

3.3.1 實例 1 ：冒泡排序

3.3.2 實例 2 ：返回斐波那契數列的前n項

3.3.3 實例 3 ：階乘遞歸

4.1 常見復雜度總結

4.2?判斷復雜度的方法

4.2.1?判斷時間復雜度的方法

4.2.2?判斷空間復雜度的方法

5. 練習

5.1 消失的數字

5.2 輪轉數組

💬 ：如果你在閱讀過程中有任何疑問或想要進一步探討的內容，歡迎在評論區暢所欲言！我們一起學習、共同成長~！

👍 ：如果你覺得這篇文章還不錯，不妨順手點個贊、加入收藏，并分享給更多的朋友噢~！

一、前言

1. 什么是數據結構

數據結構（Data Structure）是計算機存儲、組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合。

2. 什么是算法

算法（Algorithm）是明確的計算流程，它接收一個或一組輸入值，經過一系列計算步驟后，輸出一個或一組結果，其作用就是把輸入數據轉變為輸出結果。

二、時 / 空間復雜度

1. 算法效率

算法在編寫成可執行程序后，運行時需要耗費時間資源和空間（內存）資源。

因此衡量一個算法的好壞，一般從時間和空間兩個維度來衡量，即時間復雜度和空間復雜度。

時間復雜度主要衡量一個算法的運行快慢。
空間復雜度主要衡量一個算法運行所需要的額外空間。

計算機發展早期，由于存儲容量很小，所以很在乎空間復雜度。但隨著計算機行業迅速發展，如今計算機的存儲容量已達到很高程度，所以我們現在不需特別關注一個算法的空間復雜度。

2. 時間復雜度

2.1 時間復雜度的概念

時間復雜度是定量描述算法運行時間隨問題規模 N 增長的變化趨勢的函數。

理論上，算法執行耗時無法直接算出，需運行程序才知曉，但沒必要對每個算法都上機測試，于是有了時間復雜度分析。

算法耗時與語句執行次數成正比，基本操作的執行次數就是算法的時間復雜度。即，算出某條基本語句和問題規模 N 的數學表達式，就得到了該算法的時間復雜度。

// 計算一下Func1中++count語句共執行了多少次？
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);
}

這里 Func1 執行的基本操作次數：

當 N = 10 時，F (N) = 130
當 N = 100 時，F (N) = 10210
當 N = 1000 時，F (N) = 1002010

實際中計算時間復雜度時，不一定要計算精確的執行次數，只需獲知大概執行次數，此時使用大 O 的漸進表示法。

2.2 大 O 的漸進表示法

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

推導大 O 階：

用常數 1 取代運行時間中的所有加法常數。
在修改后的運行次數函數中，只保留最高階項 ?。
若最高階項存在且不是 1，則去掉該項系數 y 。得到的結果就是大 O 階 ?。

對于前面的?，

步驟 1：用常數 1 取代加法常數 10，得??。
步驟 2：只保留最高階項?。
步驟 3：最高階項??的系數為 1，無需去除，得到大 O 階 ?。

因此使用大 O 的漸進表示法后，前面 Func1 的時間復雜度為??。

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

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

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

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

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

2.3 常見的計算時間復雜度的例子

2.3.1 實例 1

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

基本操作執行次數??，所以 Func2 時間復雜度為 O(N) 。

2.3.2 實例 2

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

基本操作執行次數??，有兩個未知數 M 和 N，所以 Func3 時間復雜度為 O(N + M) 。

2.3.3 實例 3

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

基本操作執行次數 100，所以 Func4 時間復雜度為 O(1) 。

2.3.4 實例 4

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

基本操作執行最好 1 次，最壞 N 次，時間復雜度一般看最壞，所以時間復雜度為 O(N) 。

2.3.5 實例 5 ：冒泡排序

// 冒泡排序
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;}
}

基本操作執行最好? 次（數組已有序，只需進行一輪遍歷），最壞執行了? 次（? ），時間復雜度一般看最壞，所以時間復雜度為? 。

2.3.6 實例 6 ：二分查找

// 二分查找
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;
}

基本操作執行最好 1 次（第一次比較就找到目標值），最壞? 次（第 k 次比較后，搜索區間長度變為??，?得??。又因為大 O 表示法中，通常忽略對數的底數 ），所以時間復雜度為? 。有些地方寫成??。

2.3.7 實例 7 ：階乘遞歸

// 階乘遞歸
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

基本操作執行了 N 次，所以時間復雜度為 O(N) 。

2.3.8 實例 8 ：斐波那契遞歸

// 斐波那契遞歸
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

以 Fib(5)?為例，構建它的遞歸調用樹：

當 N < 3 時，F(N) = 1?；
當?N >=?3?時，F(N) = F(N - 1) + F(N - 2) +1 （+1是當前Fib(N)的這次調用）。此遞推關系的解的增長趨勢與? 同階。

又因為大 O 表示法忽略常數和低階項，所以該算法的時間復雜度為? 。

3. 空間復雜度

3.1?空間復雜度的概念

空間復雜度是用于衡量算法運行時臨時占用存儲空間大小的數學表達式。

其計算規則與時間復雜度類似，采用大O漸進表示法。

需注意，函數運行所需的棧空間（如參數、局部變量、寄存器信息等占用空間）在編譯時已確定，故空間復雜度主要看函數運行時顯式申請的額外空間。

3.2 顯式申請的額外空間

動態內存分配函數申請的空間。
部分庫函數內部會申請額外空間，C 語言標準庫中常見的如?realloc 、strdup 等。
創建某些數據結構時需專門寫代碼向系統申請內存，那么申請到的這部分內存空間就屬于額外空間。如，創建鏈表節點時得用?malloc?或?new?這些操作去申請內存。

3.3?常見的計算空間復雜度的例子

3.3.1 實例 1 ：冒泡排序

// 計算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;}
}

BubbleSort函數未通過動態內存分配函數、特定庫函數或創建復雜數據結構來顯式申請額外空間，僅使用了幾個固定的局部變量，所以它使用了常數個額外空間，其空間復雜度為?O(1)。

3.3.2 實例 2 ：返回斐波那契數列的前n項

// 計算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;
}

動態開辟了 N+1 個空間，空間復雜度為 O(N) 。

3.3.3 實例 3 ：階乘遞歸

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

Fac函數雖然未顯式地使用動態內存分配函數來申請額外空間，但遞歸調用會隱式地占用與遞歸深度成正比的棧空間，因此在計算空間復雜度時需要考慮這部分額外空間。

這里遞歸調用了 N+1 次，所以空間復雜度為 O(N) 。

4.

4.1 常見復雜度總結

基本操作執行次數/額外空間量	復雜度
常數		常數階
		線性階
		平方階
		對數階
		NlogN階
		立方階
		指數階

4.2?判斷復雜度的方法

4.2.1?判斷時間復雜度的方法

確定基本操作：如簡單賦值、算術和比較運算等，其時間復雜度為?O(1)。
分析循環：
- 單層循環：循環體為基本操作且次數與輸入規模?n?相關，復雜度為?O(n)。
- 嵌套循環：多層嵌套時，復雜度是各層循環次數乘積，如雙重嵌套為? $O(n^2)$ ，三層為? $O(n^3)$ 。
- 次數不固定循環：像二分查找，復雜度為?O(logn)。
分析遞歸函數：
- 確定深度：如階乘遞歸調用?N?次，復雜度為?O(N)。
- 考慮操作數：每次遞歸操作數固定，復雜度是深度與單次操作數乘積；若操作數與規模有關，如斐波那契遞歸，復雜度為? $O(2^n)$ 。
處理條件語句：if-else?本身?O(1)，若分支操作復雜度不同，取最壞情況，如一支?O(1)?一支?O(n)，整體為?O(n)。
確定整體復雜度：取復雜度最高部分作為整體復雜度。

4.2.2?判斷空間復雜度的方法

找基本變量：如簡單數據類型（int、float、char?等）變量占用固定空間，復雜度為?O(1)。
數據結構：
- 一維數組：數組的空間復雜度取決于數組的大小。若一維數組大小為?n，復雜度?O(n)。
- 二維數組：int arr[m][n]，復雜度?O(mn)。
- 其他：鏈表、樹、圖等，依節點數和單節點空間定，如鏈表節點數為?n?時復雜度?O(n)。
遞歸函數：
- 調用棧：遞歸深度為?n?且每次遞歸占固定空間，復雜度?O(n)。
- 數據結構：若遞歸函數中創建了數據結構，需結合結構空間和遞歸深度考量。
函數調用：
- 參數：函數參數若為大型數據結構或數組等，需考慮其占用空間對整體空間復雜度的影響。若傳遞的是指針，則通常只占固定空間，空間復雜度為 O(1)。
- 返回值：若函數返回大型數據結構，返回值占用的空間也應計入空間復雜度。
整體復雜度：取代碼各部分中復雜度最高的作為整體復雜度。

5. 練習

5.1 消失的數字

一個數組包含從0到n的所有整數，但其中缺了一個。請編寫代碼在O(n)時間內找出缺失的整數。

分析：“O(n)時間”意味著不能使用嵌套循環等。

示例：求和法

#include <stdio.h>int missingNumber(int* nums, int numsSize)
{int i = 0;int sum1 = 0;int sum2 = 0;for (i = 0; i < numsSize; i++){sum1 += nums[i];}sum2 = (numsSize * (numsSize + 1)) / 2;return sum2 - sum1;
}int main()
{int nums[] = { 9,6,4,2,3,5,7,0,1 };int size = sizeof(nums) / sizeof(nums[0]);int missnum = missingNumber(nums, size);printf("missnum=%d\n", missnum);return 0;
}

5.2 輪轉數組

給定一個整數數組，將數組中的元素向右輪轉?k?個位置。

示例：環狀替換

?
#include <stdio.h>void swap(int *a, int *b) 
{int temp = *a;*a = *b;*b = temp;
}// 向右輪轉數組函數
void rotate(int* nums, int numsSize, int k) 
{k = k % numsSize;// 處理 k > 數組長度的情況。避免不必要的重復輪轉int count = 0;for (int start = 0; count < numsSize; start++) {int current = start;// current 用于標記當前正在處理的元素的索引int prev = nums[start];do    {int next = (current + k) % numsSize;// 計算當前元素要移動到的新位置的索引// 取模確保索引在數組范圍內int temp = nums[next];nums[next] = prev;prev = temp;      // 更新 prev 為新位置的原來值current = next;   // 更新 current 為新位置的索引count++;} while (start != current);   // 回到起始位置時，說明當前的環狀替換完成，退出內層循環}
}int main() 
{int nums[] = {1, 2, 3, 4, 5, 6, 7};int numsSize = sizeof(nums) / sizeof(nums[0]);int k = 3;rotate(nums, numsSize, k);for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}?