時間復雜度

1. 什么是時間復雜度？

時間復雜度（Time Complexity）是計算算法執行時間隨輸入規模（n）增長的變化趨勢。它衡量算法的效率，通常使用大 O 記號（Big-O notation）表示，忽略低階項和常數系數。

2. 時間復雜度的用途

• 評估算法性能：幫助選擇更高效的算法，提高程序執行速度。
• 預測程序運行時間：根據輸入規模預估代碼的執行時間。
• 優化代碼：通過分析時間復雜度找到瓶頸，優化算法。

3. 常見時間復雜度及其排序

按照執行速度從快到慢排序如下：

時間復雜度	說明	示例
O(1)	常數時間	直接訪問數組元素 arr[i]
O(log n)	對數時間	二分查找
O(n)	線性時間	遍歷數組
O(n log n)	線性對數時間	快速排序、歸并排序
O(n2)	平方時間	冒泡排序、選擇排序
O(n3)	立方時間	三重嵌套循環
O(2?)	指數時間	遞歸求解斐波那契數列
O(n!)	階乘時間	旅行商問題（TSP）暴力解法

4. 如何計算時間復雜度？

方法 1：統計基本操作次數

基本操作指的是影響運行時間的核心代碼（如循環、遞歸調用等）。

方法 2：忽略常數項

時間復雜度關注增長趨勢，忽略常數。例如：

• O(2n) 簡化為 O(n)
• O(3n2 + 5n + 10) 簡化為 O(n2)

方法 3：只保留最高階項

例如：O(n2 + n) 取最高階項 O(n2)。

5. 計算示例

示例 1：遍歷數組

void loop(int arr[], int n) {for (int i = 0; i < n; i++) {  // n 次執行printf("%d", arr[i]); // O(1)}
}

• 時間復雜度：O(n)

示例 2：嵌套循環

void nestedLoop(int n) {for (int i = 0; i < n; i++) {      // O(n)for (int j = 0; j < n; j++) {  // O(n)printf("%d", i * j); // O(1)}}
}

• 時間復雜度：O(n2)

示例 3：對數復雜度

void logComplexity(int n) {for (int i = 1; i < n; i *= 2) { // i 每次翻倍printf("%d", i);}
}

• 時間復雜度：O(log n)

示例 4：遞歸復雜度

int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);
}

• 時間復雜度：O(2?)

6. 復雜度增長趨勢（直觀理解）

時間復雜度	增長趨勢
O(1)	超快，固定時間
O(log n)	很快，數據翻倍時時間增加一點
O(n)	線性增長，數據翻倍，時間也翻倍
O(n log n)	接近線性，常見于高效排序
O(n2)	慢，多用于暴力解法
O(2?)	很慢，指數爆炸
O(n!)	超級慢，幾乎無法計算大規模數據

7. 總結

• 遍歷數組：O(n)
• 嵌套循環：O(n2)
• 二分查找：O(log n)
• 遞歸斐波那契：O(2?)
• 高效算法應盡量選擇 O(n log n) 或更快的算法！ 🚀