Big O 與複雜度分析 — 時間複雜度、空間複雜度完整教學 | 資料結構與演算法

// O(1)：陣列隨機存取
// 透過記憶體位移直接計算位址，與陣列大小無關
function getElement<T>(arr: T[], index: number): T | undefined {
  return arr[index]; // 固定 1 次操作
}

// O(1)：Hash Map 查詢
function hasKey(map: Map<string, number>, key: string): boolean {
  return map.has(key); // 雜湊計算後直接定位，O(1) 平均
}

const arr = [10, 20, 30, 40, 50];
console.log(getElement(arr, 2)); // 輸出：30（無論 arr 有 5 個還是 500 萬個元素）

// O(log n)：二分搜尋
// 前提：輸入陣列必須已排序
function binarySearch(sortedArr: number[], target: number): number {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    // 使用位移運算避免大數整數溢位
    const mid = left + ((right - left) >> 1);

    if (sortedArr[mid] === target) return mid;       // 找到
    if (sortedArr[mid] < target) left = mid + 1;    // 目標在右半部
    else right = mid - 1;                            // 目標在左半部
  }

  return -1; // 未找到
}

// 每次迴圈將搜尋範圍減半 → log₂(1,000,000) ≈ 20 次即可找到
const sorted = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
console.log(binarySearch(sorted, 999_998)); // 輸出：499999

// O(n)：線性搜尋
function linearSearch<T>(arr: T[], target: T): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // 最壞情況：掃描整個陣列
  }
  return -1;
}

// O(n)：陣列加總
function sumArray(arr: number[]): number {
  // reduce 內部對每個元素訪問一次，共 n 次
  return arr.reduce((acc, val) => acc + val, 0);
}

// O(n)：找最大值
function findMax(arr: number[]): number {
  let max = arr[0];
  for (const val of arr) {
    if (val > max) max = val; // n 次比較
  }
  return max;
}

const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(sumArray(data));   // 輸出：44
console.log(findMax(data));    // 輸出：9

// O(n log n)：合併排序（Merge Sort）
// 遞迴樹有 log n 層，每層合併成本 O(n) → 總計 O(n log n)
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr; // 基礎情況

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));  // T(n/2)：排序左半部
  const right = mergeSort(arr.slice(mid));     // T(n/2)：排序右半部
  return merge(left, right);                   // O(n)：合併兩個已排序陣列
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  // 雙指標合併，每次取較小值
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // 接上剩餘元素
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const unsorted = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(unsorted)); // 輸出：[3, 9, 10, 27, 38, 43, 82]

// O(n²)：氣泡排序（Bubble Sort）
function bubbleSort(arr: number[]): number[] {
  const result = [...arr];
  const n = result.length;

  for (let i = 0; i < n - 1; i++) {           // 外層：n 輪
    for (let j = 0; j < n - i - 1; j++) {     // 內層：每輪最多 n 次比較
      if (result[j] > result[j + 1]) {
        // 交換相鄰元素
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
      }
    }
  }

  return result;
  // 總比較次數 = n(n-1)/2 ≈ n²/2 = O(n²)
}

// O(n²)：判斷陣列中是否有重複元素（暴力法）
function hasDuplicateBrute(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true; // 找到重複
    }
  }
  return false;
}

// 更好的解法：O(n) 使用 Set
function hasDuplicateFast(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}

const testArr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(testArr));          // 輸出：[11, 12, 22, 25, 34, 64, 90]
console.log(hasDuplicateFast([1, 2, 3, 2])); // 輸出：true

// O(2ⁿ)：費波那契數列（樸素遞迴）
// 遞迴樹每層節點數加倍 → 總節點數 ≈ 2ⁿ
function fibNaive(n: number): number {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2); // 兩個遞迴呼叫
}

// O(n)：加入記憶化，空間換時間
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!; // 已計算過，直接回傳

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result); // 儲存結果供後續使用
  return result;
}

console.log(fibNaive(10));  // 輸出：55（但 fibNaive(50) 需要等很久）
console.log(fibMemo(50));   // 輸出：12586269025（瞬間完成）

// complexity_demo.cpp
// 編譯：g++ -O2 -std=c++20 complexity_demo.cpp -o complexity_demo
#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>

// 計時輔助（對應 TypeScript 的 performance.now()）
template <typename Fn>
double measureMs(Fn&& fn) {
  auto start = std::chrono::high_resolution_clock::now();
  fn();
  auto end = std::chrono::high_resolution_clock::now();
  return std::chrono::duration<double, std::milli>(end - start).count();
}

// ── O(1)：常數時間 ──────────────────────────────────────────
// C++ vector 和 TS Array 一樣，隨機存取為 O(1)
int getElement(const std::vector<int>& v, std::size_t idx) {
  return v[idx]; // 直接記憶體位移，與 n 無關
}

// ── O(log n)：二分搜尋 ──────────────────────────────────────
// C++ 提供 STL std::lower_bound，內部即為二分搜尋
int binarySearch(const std::vector<int>& v, int target) {
  // 差異：C++ 慣用迭代器（iterator），TS 直接操作索引
  auto it = std::lower_bound(v.begin(), v.end(), target);
  if (it != v.end() && *it == target) {
    return static_cast<int>(std::distance(v.begin(), it));
  }
  return -1;
}

// ── O(n)：線性加總 ──────────────────────────────────────────
// std::accumulate 對應 TS 的 Array.reduce
long long sumArray(const std::vector<int>& v) {
  return std::accumulate(v.begin(), v.end(), 0LL);
}

// ── O(n log n)：排序 ─────────────────────────────────────────
// std::sort 使用 introsort（平均 O(n log n)），對應 TS 的 Array.sort
std::vector<int> sortArray(std::vector<int> v) {
  std::sort(v.begin(), v.end()); // 傳值，不修改原始陣列
  return v;
}

// ── O(n²)：氣泡排序 ──────────────────────────────────────────
std::vector<int> bubbleSort(std::vector<int> v) {
  int n = static_cast<int>(v.size());
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < n - i - 1; ++j) {
      if (v[j] > v[j + 1]) std::swap(v[j], v[j + 1]); // C++ std::swap
    }
  }
  return v;
}

int main() {
  const std::vector<std::size_t> sizes = {1'000, 10'000, 100'000};

  for (auto n : sizes) {
    std::vector<int> sorted(n);
    std::iota(sorted.begin(), sorted.end(), 0); // 填入 0, 1, 2, ..., n-1

    std::vector<int> unsorted(n);
    for (auto& x : unsorted) x = rand() % static_cast<int>(n);

    std::cout << "\n=== n = " << n << " ===\n";

    auto t1 = measureMs([&]{ getElement(sorted, n / 2); });
    std::cout << "O(1)       getElement:   " << t1 << "ms\n";

    auto t2 = measureMs([&]{ binarySearch(sorted, static_cast<int>(n) - 1); });
    std::cout << "O(log n)   binarySearch: " << t2 << "ms\n";

    auto t3 = measureMs([&]{ sumArray(sorted); });
    std::cout << "O(n)       sumArray:     " << t3 << "ms\n";

    auto t4 = measureMs([&]{ sortArray(unsorted); });
    std::cout << "O(n log n) std::sort:    " << t4 << "ms\n";

    if (n <= 10'000) {
      auto t5 = measureMs([&]{ bubbleSort(unsorted); });
      std::cout << "O(n²)      bubbleSort:   " << t5 << "ms\n";
    }
  }
  return 0;
}

/*
預期輸出（n = 10,000）：
O(1)       getElement:   0.0001ms
O(log n)   binarySearch: 0.0003ms
O(n)       sumArray:     0.0500ms
O(n log n) std::sort:    0.5000ms
O(n²)      bubbleSort:   200.000ms  ← n 增加 10x 時間增加 100x
*/

// 模擬動態陣列擴容，觀察攤銷 O(1) 的運作方式
class DynamicArray<T> {
  private data: T[];
  private _size: number = 0;
  private _capacity: number = 1;

  constructor() {
    this.data = new Array(this._capacity);
  }

  push(item: T): void {
    if (this._size === this._capacity) {
      this._resize(); // O(n)，但很少觸發
    }
    this.data[this._size++] = item; // O(1)
  }

  private _resize(): void {
    this._capacity *= 2; // 容量加倍策略
    const newData = new Array(this._capacity);
    for (let i = 0; i < this._size; i++) {
      newData[i] = this.data[i]; // 複製舊資料 O(n)
    }
    this.data = newData;
    console.log(`  [resize] capacity → ${this._capacity}`);
  }

  get size(): number { return this._size; }
  get capacity(): number { return this._capacity; }
}

// 追蹤擴容時機：push 第 2、3、5、9、17 個時觸發
const dynArr = new DynamicArray<number>();
for (let i = 1; i <= 20; i++) {
  dynArr.push(i);
}
// n 次 push 的總複製成本 = 1 + 2 + 4 + ... + n/2 < 2n = O(n)
// 平均每次 push 的攤銷成本 = O(n) / n = O(1)

function mystery1(n: number): number {
  let count = 0;
  for (let i = n; i > 0; i = Math.floor(i / 2)) {
    count++;
  }
  return count;
  // 分析：i 每次除以 2，需要 log₂(n) 次後降為 0
  // 答案：O(log n)
}

// 暴力法 O(n²)
function hasDuplicateBrute(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// 優化：Set 查詢 O(1)，整體 O(n)
function hasDuplicateOptimal(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false; // 空間複雜度：O(n)
}

// 樸素遞迴 O(2ⁿ)：每個節點產生兩個子問題
function fibBad(n: number): number {
  if (n <= 1) return n;
  return fibBad(n - 1) + fibBad(n - 2);
}

// 記憶化 O(n)：每個子問題只計算一次
function fibGood(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fibGood(n - 1, memo) + fibGood(n - 2, memo);
  return memo.set(n, result), result;
}

// ❌ 誤以為兩個 for 迴圈 = O(n²)
function twoLoopsAdd(arr: number[]): void {
  for (const x of arr) console.log(x);  // O(n)
  for (const x of arr) console.log(x);  // O(n)
  // 總計：O(n) + O(n) = O(2n) = O(n)，兩個獨立迴圈相加！
}

// ✓ 只有巢狀迴圈才相乘
function twoLoopsMultiply(arr: number[]): void {
  for (const x of arr) {
    for (const y of arr) { // 巢狀 → O(n) × O(n) = O(n²)
      console.log(x, y);
    }
  }
}

// ❌ 誤以為這是 O(n)，實際是 O(n²)
function removeDuplicatesBad(arr: number[]): number[] {
  const result: number[] = [];
  for (const x of arr) {
    if (!result.includes(x)) { // Array.includes 是 O(n)！
      result.push(x);
    }
  }
  return result; // O(n) × O(n) = O(n²)
}

// ✓ 正確：使用 Set，O(1) 查詢
function removeDuplicatesGood(arr: number[]): number[] {
  return [...new Set(arr)]; // O(n) 時間，O(n) 空間
}