一 概念

在 C++ 中，時間復雜度是衡量算法運行時間隨輸入規模增長的趨勢的關鍵指標，用于評估算法的效率。它通過?大 O 表示法（Big O Notation）?描述，關注的是輸入規模?n?趨近于無窮大時，算法時間增長的主導因素（忽略常數和低階項）。

• 輸入規模（n）：算法處理的數據量（如數組長度、鏈表節點數、矩陣維度等）。
• 大 O 表示法：表示算法時間復雜度的上界，例如?O(n)?表示時間與輸入規模?n?成線性關系。
• 核心原則：只保留最高階項，忽略常數因子和低階項（如?O(2n + 3)?簡化為?O(n)，O(n2 + n)?簡化為?O(n2)）。

二 常見時間復雜度類型?

1.O (1)：常數時間

無論輸入規模多大，算法執行時間恒定（與?n?無關）。

典型場景：

• 數組 /vector?的隨機訪問（通過下標?[i]）。
• 哈希表（unordered_map）的插入、查找（平均情況）。

示例：訪問數組元素?

#include <vector>int get_element(const std::vector<int>& vec, int index) {return vec[index];  // 隨機訪問，時間復雜度 O(1)
}

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

時間與輸入規模?n?成正比，需逐個處理每個元素。
典型場景：

• 線性枚舉（遍歷數組、鏈表等）。
• 未排序數組的順序查找。

示例：遍歷?vector?求和

#include <vector>int sum_vector(const std::vector<int>& vec) {int sum = 0;for (int num : vec) {  // 遍歷所有元素，時間復雜度 O(n)sum += num;}return sum;
}

3.?O (logn)：對數時間

時間隨輸入規模的對數增長，通常出現在分治算法中（如二分查找）。
典型場景：

• 有序數組的二分查找（std::lower_bound）。
• 平衡二叉搜索樹（如?std::set、std::map）的插入、查找。

示例：二分查找（C++ 標準庫實現）

#include <vector>
#include <algorithm>  // for std::lower_bound// 查找目標值的位置（返回迭代器）
auto binary_search(const std::vector<int>& vec, int target) {return std::lower_bound(vec.begin(), vec.end(), target);// 時間復雜度 O(logn)（數組已排序）
}

4.?O (nlogn)：線性對數時間

時間增長趨勢為?n × logn，常見于高效的排序算法。
典型場景：

• 快速排序、歸并排序（平均情況）。
• std::sort（C++ 標準庫排序，基于快速排序 / 堆排序）。

示例：使用?std::sort?排序

#include <vector>
#include <algorithm>void sort_vector(std::vector<int>& vec) {std::sort(vec.begin(), vec.end());  // 平均時間復雜度 O(nlogn)
}

5.O (n2)：平方時間

時間與輸入規模的平方成正比，常見于雙重循環的暴力算法。
典型場景：

• 冒泡排序、選擇排序（最壞 / 平均情況）。
• 二維數組的遍歷（如矩陣元素逐個處理）。

示例：冒泡排序

#include <vector>void bubble_sort(std::vector<int>& vec) {int n = vec.size();for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {  // 雙重循環，時間復雜度 O(n2)if (vec[j] > vec[j + 1]) {std::swap(vec[j], vec[j + 1]);}}}
}

6.?其他復雜度

• O(2?)：指數時間（如斐波那契數列的遞歸實現，存在大量重復計算）。
• O(n!)：階乘時間（如全排列生成）。

三、時間復雜度的分析方法?

1.?單循環：O (n)

單個循環遍歷?n?次，時間復雜度為?O(n)。

for (int i = 0; i < n; ++i) {// 操作（時間復雜度 O(1)）
}
// 總時間復雜度：O(n)

2.?雙重循環：O (n2)

外層循環?n?次，內層循環?n?次，總次數為?n × n = n2。

for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {// 操作（O(1)）}
}
// 總時間復雜度：O(n2)

當外層循環到第 i 次時，內層循環 i 次，總次數為?(1 + n)n / 2 = (n + n^2) / 2次。

for (int i = 0; i < n; ++i) {for (int j = 0; j <= i; ++j) {//操作（O(1)）}
}
/*  i  0  1  2  3  ...  n-1j  1  1  2  3  ...  n總操作次數為等差數列：(1 + n)n / 2 = (n + n^2) / 2只保留最高階項，忽略常數因子和低階項，故時間復雜度O(n^2)
*/

3.?對數循環：O (logn)

每次循環將問題規模減半（如二分查找）。

int i = 1;
while (i < n) {i *= 2;  // 每次規模翻倍
}
// 循環次數為 log?n，時間復雜度 O(logn)

int i = n * n;
while (i != 1) {i /= 2; //每次規模減少為原來的一半
}/*
t(操作次數) 0       1           2            3     ...
i          n^2   n^2 / 2     n^2 / 4      n^2 / 8  ...由上面規律可得：i = n^2 / 2^t
將該表達式與 i = 1 聯立
得 t = 2log2(n)
所以時間復雜度為 O(log2(n)),記為 O(logn)
*/

4.?遞歸的時間復雜度

遞歸的時間復雜度需結合遞歸深度和每層操作次數。
示例：斐波那契數列的遞歸實現（低效版）

int fib(int n) {if (n <= 1) return n;return fib(n - 1) + fib(n - 2);  // 每次遞歸分裂為 2 個子問題
}
// 時間復雜度：O(2?)（存在大量重復計算）

四、時間復雜度的優化策略

1.?用哈希表優化查找（O (n) → O (1)）

將線性查找（O (n)）替換為哈希表（unordered_map）的鍵值查找（O (1)），以空間換時間。

示例：兩數之和。在數組中找到兩個元素值等于target，返回這兩個元素組成的數組。

#include <vector>
#include <unordered_map>std::vector<int> two_sum(const std::vector<int>& nums, int target) {std::unordered_map<int, int> hash;  // 哈希表存儲值→索引for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i];if (hash.count(complement)) {  // 查找時間 O(1)return {hash[complement], i};}hash[nums[i]] = i;  // 插入時間 O(1)}return {};
}
// 原暴力解法時間復雜度 O(n2)，優化后 O(n)

2.?用排序 + 二分查找優化（O (n2) → O (nlogn)）

將雙重循環的暴力匹配替換為排序后二分查找。
示例：查找數組中是否存在兩數之和為目標值

#include <vector>
#include <algorithm>bool has_two_sum(std::vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());  // 排序 O(nlogn)for (int num : nums) {int complement = target - num;// 二分查找 complement，時間 O(logn)if (std::binary_search(nums.begin(), nums.end(), complement)) {return true;}}return false;
}
// 原暴力解法 O(n2)，優化后 O(nlogn)

3.?避免重復計算（O (2?) → O (n)）

通過動態規劃或記憶化搜索，消除遞歸中的重復子問題。
示例：斐波那契數列的動態規劃實現

#include <vector>int fib(int n) {if (n <= 1) return n;std::vector<int> dp(n + 1);  // 存儲已計算的結果dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];  // 避免重復計算，時間 O(n)}return dp[n];
}
// 原遞歸解法 O(2?)，優化后 O(n)

五 總結

時間復雜度反映算法運行時間隨輸入規模增長的趨勢，不同復雜度的增長速度從低到高排列如下：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2)

時間復雜度是評估算法效率的核心指標。在 C++ 中，通過分析循環嵌套、遞歸深度或操作次數，可以確定算法的時間復雜度。實際編碼時，應優先選擇低時間復雜度的算法（如 O (nlogn) 優于 O (n2)），并利用哈希表、排序 + 二分等優化手段降低復雜度。同時，結合數據結構的特性（如unordered_map的 O (1) 查找），可以顯著提升程序性能。