時間復(fù)雜度

1. 什么是時間復(fù)雜度？

時間復(fù)雜度（Time Complexity）描述的是 算法的運行時間如何隨著輸入數(shù)據(jù)規(guī)模（n）的增長而變化。 即時間或空間隨數(shù)據(jù)規(guī)模增長的變化趨勢。
時間復(fù)雜度通常用 大 O 表示法（Big-O Notation） 表示，如 O(1)、O(n)、O(log n) 等。
它們是計算機(jī)科學(xué)中非常重要的概念，尤其在面試和優(yōu)化代碼時經(jīng)常被問到。

2. 常見時間復(fù)雜度對比

3. 詳細(xì)解釋

（1）O(1) — 常數(shù)時間

• 特點：操作時間與數(shù)據(jù)規(guī)模 n 無關(guān)，無論 n 多大，耗時固定。
• 例子：
  • 數(shù)組按索引訪問：arr[5] 直接跳轉(zhuǎn)到內(nèi)存地址，無需遍歷。
  • 哈希表（HashMap）查找：通過哈希函數(shù)計算位置，理想情況下一次找到。
• 代碼示例：

  int[] arr = {1, 2, 3};
  int x = arr[1]; // O(1)，直接訪問索引 1
  

（2）O(log n) — 對數(shù)時間

• 特點：操作時間隨 n 增長呈對數(shù)增長（增長速度遠(yuǎn)慢于線性）。
• 核心思想：每一步將問題規(guī)模減半（如二分查找）。
• 例子：
  • 二分查找：在有序數(shù)組中查找元素，每次排除一半數(shù)據(jù)。
  • 平衡二叉搜索樹（如 TreeMap）：每次比較縮小搜索范圍。
• 代碼示例：

  // 二分查找（O(log n)）
  int binarySearch(int[] arr, int target) {
      int left = 0, right = arr.length - 1;
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if (arr[mid] == target) return mid;
          else if (arr[mid] < target) left = mid + 1;
          else right = mid - 1;
      }
      return -1;
  }
  

（3）O(n) — 線性時間

• 特點：操作時間與數(shù)據(jù)規(guī)模 n 成正比。
• 例子：
  • 遍歷數(shù)組/鏈表：需要逐個訪問每個元素。
  • 線性搜索：在無序列表中查找特定值。
• 代碼示例：

  // 遍歷數(shù)組（O(n)）
  for (int num : arr) {
      System.out.println(num);
  }
  

（4）O(n log n) — 線性對數(shù)時間

• 特點：常見于高效排序算法，比 O(n2) 快，但比 O(n) 慢。
• 例子：
  • 快速排序、歸并排序：通過分治策略減少比較次數(shù)。
• 代碼示例：

  Arrays.sort(arr); // Java 默認(rèn)使用快速排序（O(n log n)）
  

（5）O(n2) — 平方時間

• 特點：操作時間與 n2 成正比，性能較差。
• 例子：
  • 冒泡排序、選擇排序：嵌套循環(huán)遍歷所有元素對。
  • 嵌套循環(huán)：如遍歷二維數(shù)組。
• 代碼示例：

  // 冒泡排序（O(n2)）
  for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
          if (arr[i] > arr[j]) swap(arr, i, j);
      }
  }
  

4. 如何直觀理解？

假設(shè) n = 1000（數(shù)據(jù)量）：

5. 為什么重要？

• 優(yōu)化代碼：選擇更低時間復(fù)雜度的算法可以大幅提升性能（尤其是大數(shù)據(jù)量時）。
• 面試必考：大廠面試常要求分析代碼的時間復(fù)雜度。
• 系統(tǒng)設(shè)計：高并發(fā)場景下，O(n2) 的算法可能導(dǎo)致服務(wù)崩潰。

6. 常見誤區(qū)

1. 忽略常數(shù)項：
   O(2n) 和 O(100n) 都記作 O(n)，因為大 O 表示法關(guān)注的是增長趨勢。
2. 混淆最好/最壞情況：
   比如快速排序的最壞時間復(fù)雜度是 O(n2)（當(dāng)數(shù)組已排序時），但平均是 O(n log n)。
3. 忽視空間復(fù)雜度：
   有些算法（如歸并排序）時間高效但需要額外空間（O(n)）。

空間復(fù)雜度

空間復(fù)雜度（Space Complexity） 是衡量算法在運行過程中臨時占用存儲空間大小的量度，表示算法所需的額外內(nèi)存空間隨輸入數(shù)據(jù)規(guī)模（n）增長的變化趨勢。和時間復(fù)雜度一樣，空間復(fù)雜度也用大 O 表示法（Big-O Notation）描述。

1. 空間復(fù)雜度的核心概念

• 額外空間：指除了輸入數(shù)據(jù)本身占用的空間外，算法運行所需的臨時存儲空間（如變量、棧空間、遞歸調(diào)用等）。
• 原地算法（In-place）：空間復(fù)雜度為 O(1) 的算法，即不需要額外空間（如冒泡排序、堆排序）。
• 非原地算法：需要額外空間的算法（如歸并排序 O(n)）。

2. 常見空間復(fù)雜度對比

3. 具體示例分析

(1) O(1) — 常數(shù)空間

算法運行期間，額外空間固定，與輸入規(guī)模 n 無關(guān)。

// 示例：交換兩個變量的值（無需額外數(shù)組）
void swap(int a, int b) {
    int temp = a; // 僅用 1 個臨時變量
    a = b;
    b = temp;
}

典型算法：

• 冒泡排序、選擇排序、插入排序（原地排序）。

(2) O(n) — 線性空間

額外空間與輸入規(guī)模 n 成正比。

// 示例：將數(shù)組復(fù)制到新數(shù)組
int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length]; // 額外空間 O(n)
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

典型算法：

• 歸并排序（需臨時數(shù)組）、哈希表（存儲鍵值對）、遞歸調(diào)用棧（最壞情況）。

(3) O(log n) — 對數(shù)空間

常見于遞歸算法，每次遞歸調(diào)用減少問題規(guī)模。

// 示例：二分查找的遞歸實現(xiàn)
int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) {
        return binarySearch(arr, target, mid + 1, right); // 遞歸調(diào)用
    } else {
        return binarySearch(arr, target, left, mid - 1);
    }
}

典型算法：

• 快速排序的遞歸調(diào)用棧（平均 O(log n)，最壞 O(n)）、平衡二叉樹的遞歸操作。

(4) O(n2) — 平方空間

常見于需要二維數(shù)組的算法。

// 示例：動態(tài)規(guī)劃中的二維表格
int[][] dp = new int[n][n]; // 空間 O(n2)

典型場景：

• 動態(tài)規(guī)劃問題（如最長公共子序列）、鄰接矩陣存儲圖。

4. 空間復(fù)雜度 vs 時間復(fù)雜度

5. 實際應(yīng)用中的權(quán)衡

• 內(nèi)存敏感場景（如嵌入式設(shè)備）：優(yōu)先選擇空間復(fù)雜度低的算法（如原地排序）。
• 時間敏感場景（如實時系統(tǒng)）：可能犧牲空間換取時間（如用哈希表加速查找）。

6. 常見誤區(qū)

1. 混淆“輸入空間”和“額外空間”：
   空間復(fù)雜度通常只計算算法運行時額外申請的空間，輸入數(shù)據(jù)本身不納入計算。

   // 以下算法的空間復(fù)雜度是 O(1)，而非 O(n)
   void printArray(int[] arr) { // arr 是輸入，不計算
       for (int num : arr) {
           System.out.println(num);
       }
   }
   

2. 忽略遞歸調(diào)用的?？臻g：
   遞歸算法的空間復(fù)雜度取決于遞歸深度（如斐波那契數(shù)列遞歸版為 O(n)）。

總結(jié)

• 空間復(fù)雜度 關(guān)注算法對內(nèi)存的額外消耗。
• 常見級別：O(1) < O(log n) < O(n) < O(n2)。
• 優(yōu)化策略：根據(jù)場景選擇時間或空間更優(yōu)的算法，例如：
  • 內(nèi)存有限時用堆排序（O(1) 空間），而非歸并排序（O(n) 空間）。
  • 遞歸算法可改為迭代版本以減少?？臻g（如用循環(huán)實現(xiàn)斐波那契數(shù)列）。

理解對數(shù) log

在時間復(fù)雜度 O(log n) 中，log 指的是 對數(shù)（logarithm），通常默認(rèn)以 2 為底（即 log? n），表示的是“將問題規(guī)模 n 不斷除以 2，直到結(jié)果為 1 所需的次數(shù)”。這種對數(shù)增長的特點是：數(shù)據(jù)量 n 大幅增加時，操作次數(shù)增長非常緩慢。

1. 為什么是 log? n？

• 二分思想：O(log n) 常見于分治算法（如二分查找、平衡二叉樹操作），每一步都將問題規(guī)模 減半，因此底數(shù)默認(rèn)為 2。
  • 例如：二分查找每次排除一半數(shù)據(jù)，直到找到目標(biāo)。
• 數(shù)學(xué)定義：
  log? n = x 等價于 2? = n。
  即“2 的 x 次方等于 n”。

2. 為什么 n=1000 時操作次數(shù)約為 10？

計算 log? 1000：

1. 手動估算：
   • 21? = 1024 ≈ 1000，因此 log? 1000 ≈ 10。
2. 精確計算：
   • log? 1000 ≈ 9.96578，向上取整為 10 次操作。

直觀理解：
在二分查找中，若數(shù)組長度為 1000，最壞情況下需要 約 10 次比較 才能確定元素是否存在：

第1次：1000 → 剩余 500  
第2次：500  → 剩余 250  
第3次：250  → 剩余 125  
...  
第10次：1    → 找到或確認(rèn)不存在

3. 不同底數(shù)的 log 會影響時間復(fù)雜度嗎？

• 大 O 表示法忽略常數(shù)：無論底數(shù)是 2、10 還是自然對數(shù) e，O(log? n)、O(log?? n) 和 O(ln n) 都記作 O(log n)，因為對數(shù)之間可以通過換底公式轉(zhuǎn)換（相差一個常數(shù)系數(shù)）。
  換底公式：
  log? b = log? c × log_c b
  例如：log?? n = log?? 2 × log? n ≈ 0.301 × log? n（常數(shù)可忽略）。

4. 為什么 O(log n) 高效？

對比其他復(fù)雜度（假設(shè) n=1,000,000）：

結(jié)論：
O(log n) 幾乎接近常數(shù)時間，即使 n 非常大（如 10 億），操作次數(shù)也僅需 約 30 次（因為 log? 1,000,000,000 ≈ 29.9）。

5. 常見 O(log n) 的算法場景

1. 二分查找：在有序數(shù)組中查找元素。
2. 平衡二叉搜索樹（如 TreeMap）：插入、刪除、查找。
3. 分治算法：如快速排序的劃分過程（平均 O(n log n)）。
4. 堆操作：插入、刪除堆頂元素（O(log n)）。

6. 數(shù)學(xué)推導(dǎo)示例（二分查找）

假設(shè)數(shù)組長度為 n，最壞情況下查找次數(shù)為 x，則：

n / 2 / 2 / ... / 2 = 1  →  n / 2? = 1  →  2? = n  →  x = log? n

因此，二分查找的時間復(fù)雜度為 O(log n)。

總結(jié)

• log 默認(rèn)以 2 為底，表示問題規(guī)模不斷減半的次數(shù)。
• n=1000 時 log? n ≈ 10，因為 21? ≈ 1000。
• O(log n) 是極其高效的時間復(fù)雜度，適用于分治策略的算法（如二分查找、平衡樹操作）。

常用算法的復(fù)雜度整理

以下是常用算法的復(fù)雜度整理表格，涵蓋 排序算法、查找算法、數(shù)據(jù)結(jié)構(gòu)操作 等，并標(biāo)注最佳、平均和最壞情況：

1. 排序算法時間復(fù)雜度

說明：

• k：桶的數(shù)量或計數(shù)范圍（非比較排序算法依賴數(shù)據(jù)范圍）。
• 穩(wěn)定：相等元素的相對順序是否保持不變。

2. 查找算法時間復(fù)雜度

說明：

• 哈希表的最壞情況（O(n)）發(fā)生在所有鍵哈希沖突時（退化為鏈表）。
• 二叉搜索樹若不平衡（如退化成鏈表），查找效率降至 O(n)。

3. 數(shù)據(jù)結(jié)構(gòu)操作時間復(fù)雜度

說明：

• 數(shù)組的插入/刪除需移動元素（除非在末尾操作）。
• 鏈表的插入/刪除在已知節(jié)點時為 O(1)，但查找仍需 O(n)。

4. 關(guān)鍵結(jié)論

1. 排序算法：
   • 最快平均時間：快速排序、歸并排序、堆排序（O(n log n)）。
   • 穩(wěn)定排序：歸并排序、計數(shù)排序、基數(shù)排序。
2. 查找算法：
   • 哈希表 平均 O(1)，但需處理沖突。
   • 二分查找 僅適用于有序數(shù)組（O(log n)）。
3. 數(shù)據(jù)結(jié)構(gòu)選擇：
   • 頻繁查找：用哈希表（O(1)）。
   • 有序數(shù)據(jù)：用平衡樹（O(log n)）。
   • 快速插入/刪除：用鏈表（O(1)）。

附：復(fù)雜度增長趨勢對比圖

n=16 時：
O(1)      → 1
O(log n)  → 4
O(n)      → 16
O(n log n)→ 64
O(n2)     → 256
O(2?)     → 65,536

掌握這些復(fù)雜度規(guī)律，可以高效選擇算法和數(shù)據(jù)結(jié)構(gòu)！