複雜度速查表 — 經典演算法與資料結構

O(1) < O(log N) < O(√N) < O(N) < O(N log N) < O(N²) < O(N³) < O(2^N) < O(N!)

S = N + N/2 + N/4 + N/8 + ...
  = N × (1 + 1/2 + 1/4 + 1/8 + ...)
  = N × 1/(1 - 1/2)      ← geometric series formula: 1/(1-r) for |r| < 1
  = N × 2
  = 2N

Example: Heapify (build heap from array)
  - Leaf level (N/2 nodes): 0 swaps each   → N/2 × 0
  - Level above (N/4 nodes): 1 swap each   → N/4 × 1
  - Level above (N/8 nodes): 2 swaps each  → N/8 × 2
  - ...
  - Root (1 node): log N swaps             → 1 × log N

  Total = N/4 + 2·N/8 + 3·N/16 + ...
        = N × (1/4 + 2/8 + 3/16 + ...) ≈ N
  → O(N)  ← This is why heapify is O(N), not O(N log N)!

Example: Segment tree build
  - Leaf nodes: N
  - Internal nodes: N - 1
  - Work at each node: O(1)
  → Total: O(N)

Example: Amortized cost of dynamic array doubling
  Insert N elements:
  Copies at resizes: 1 + 2 + 4 + 8 + ... + N = 2N
  → Amortized O(1) per insert

Level 0:   1 merge of size N     → N work
Level 1:   2 merges of size N/2  → N work
Level 2:   4 merges of size N/4  → N work
...
Level k:   2^k merges of size N/2^k → N work

Total levels = log₂(N)
Total work   = N × log₂(N)
→ O(N log N)

Geometric (converging):     Merge Sort (constant per level):
Level 0:  N                 Level 0:  N
Level 1:  N/2               Level 1:  N/2 + N/2 = N
Level 2:  N/4               Level 2:  N/4+N/4+N/4+N/4 = N
Level 3:  N/8               Level 3:  N
...                         ...
Sum ≈ 2N  ✓ O(N)            Sum = N × log N  ✓ O(N log N)

N = 8, getNodeByIdx(head, mid) ≈ O(N) per call

Level 0:  build(0..7)                             → scan ~N    = N
Level 1:  build(0..2) + build(4..7)               → N/2 + N/2  = N
Level 2:  build(0..0)+build(2..2)+build(4..5)+... → N/4×4      = N
Level 3:  8 leaf calls                             → N/8×8      = N

                N
           /         \
        N/2           N/2
       /   \         /   \
     N/4   N/4    N/4   N/4

Total = N + N + N + ... (log N times) = N × log N → O(N log N)

Heapify:        N/2 + N/4 + N/8 + ... = N  →  O(N)      (work HALVES per level)
BST from list:  N   + N   + N   + ... = N log N → O(N log N) (work CONSTANT per level)

Space complexity for DFS recursion = maximum recursion stack depth
                                    = tree height

build(root)           ← frame 1 on stack
  -> build(left)      ← frame 2 on stack
       -> build(left) ← frame 3 on stack
            -> null   ← returns, pops frame 3

Balanced BST built:
        4
      /   \
     2     6
    / \   / \
   1   3 5   7

Tree height = 3

Max stack at any moment (going down leftmost path):
  build(0,6)  → root 4   ← frame 1
  build(0,2)  → root 2   ← frame 2
  build(0,0)  → root 1   ← frame 3
  build(0,-1) → null     ← frame 4, then returns

Stack depth ≈ log₂(7) ≈ 3

1
 \
  2
   \
    3       ← each node is a stack frame → O(N) depth
     \
      4

Algorithm Variant              | Time        | Space    | How?
-------------------------------|-------------|----------|--------------------------------------
V0-1: getNodeByIdx (from head) | O(N log N)  | O(log N) | N scan × log N levels; balanced tree
V0-2: slow/fast pointer        | O(N log N)  | O(log N) | O(N) per split × log N levels
V0-3: in-order simulation      | O(N)        | O(log N) | advance pointer once per node (!)

Interview rule of thumb for recursion:
  Space = recursion stack depth
  Balanced tree → O(log N)
  Skewed tree   → O(N)
  N work per level × log N levels → O(N log N)  ← "merge sort" pattern

S = 1 + 2 + 3 + ... + N
  = N(N+1)/2
  ≈ N²/2
  → O(N²)

Bubble sort comparisons:
  Round 1: N-1 comparisons
  Round 2: N-2 comparisons
  ...
  Round N-1: 1 comparison
  Total = (N-1) + (N-2) + ... + 1 = N(N-1)/2 → O(N²)

Counting all pairs in array:
  For each i, compare with all j > i
  Total pairs = N(N-1)/2 → O(N²)

log₂(N) ≈ ln(N) / 0.693           # log base conversion
log₂(N²) = 2 log₂(N)              # power rule
log₂(N·M) = log₂(N) + log₂(M)    # product rule
log₂(2^N) = N                     # inverse

2^(log₂ N) = N                    # inverse
log₂(N!) ≈ N log₂ N  (Stirling)   # N! ≈ (N/e)^N × √(2πN)

How many times can you halve N before reaching 1?
  → log₂(N) times   (binary search, tree height)

How many times can you double 1 before reaching N?
  → log₂(N) times   (binary tree levels)

N = 10^9 operations → too slow for 1 second (typical limit: 10^8 ops/sec)
N = 10^6 → fine for O(N log N)
N = 10^5 → fine for O(N²)... barely
N = 20   → OK for O(2^N)
N = 12   → OK for O(N!)

H(N) = 1 + 1/2 + 1/3 + ... + 1/N ≈ ln(N) ≈ O(log N)

Sieve of Eratosthenes: O(N log log N)
  - Cross out multiples of 2: N/2 ops
  - Cross out multiples of 3: N/3 ops
  - Cross out multiples of 5: N/5 ops
  - Total ≈ N × (1/2 + 1/3 + 1/5 + ...) = N × log log N

Average case of Quick Sort partitioning ≈ O(N log N)

Subsets of N elements:       2^N
Permutations of N elements:  N!
Combinations C(N, K):        N! / (K! × (N-K)!)

Stirling's approximation:    N! ≈ √(2πN) × (N/e)^N
→ log(N!) ≈ N log N         (explains why permutation algos are O(N log N) in log space)

Compare f(N) vs N^(log_b(a)):

Case 1: f(N) = O(N^(log_b(a) - ε))  →  T(N) = O(N^log_b(a))
Case 2: f(N) = Θ(N^log_b(a))         →  T(N) = O(N^log_b(a) × log N)
Case 3: f(N) = Ω(N^(log_b(a) + ε))  →  T(N) = O(f(N))

'a' - 'A' = 32     (difference between lowercase and uppercase)
'a' = 97,  'A' = 65
'z' = 122, 'Z' = 90
'0' = 48,  '9' = 57

Detect same letter different case:
  Math.abs(char1 - char2) == 32   → O(1) check
  (see LC 1544 Make The String Great)

Convert case:
  lowercase → uppercase:  c - 32  (or c & ~32 or c ^ 32)
  uppercase → lowercase:  c + 32  (or c | 32)

Index in alphabet:
  c - 'a'  (0-indexed: 'a'→0, 'b'→1, ..., 'z'→25)
  c - 'A'  (same for uppercase)

Balanced BST / heap:     O(log N)  ← tree height
Skewed BST / linked list: O(N)     ← degenerates to linear
General graph DFS:        O(V)

O(1) extra space tricks:
  - Two pointers (reverse array, palindrome)
  - Floyd's cycle detection
  - Morris tree traversal
  - Partition in-place (quick sort, Dutch flag)
  - Bit manipulation for visited flags (if N ≤ 64)

Problem                 | Naive Space | Optimized Space | Time Trade-off
------------------------|-------------|-----------------|---------------
DP (2D → 1D rolling)   | O(M·N)      | O(N)            | Same time
Memoization → Bottom-up| O(N) stack  | O(1) or O(N)    | Same time
Fibonacci               | O(N)        | O(1)            | Same O(N)
KMP vs Naive search     | O(M)        | —               | O(N+M) vs O(N·M)

Input Size → Reasonable Complexity:

N ≤ 10        → O(N!) or O(2^N)     backtracking, all permutations
N ≤ 20        → O(2^N)              bitmask DP, subsets
N ≤ 100       → O(N³)               Floyd-Warshall, 3-loop DP
N ≤ 1,000     → O(N²)               nested loops, naive DP
N ≤ 100,000   → O(N log N)          sorting, heap, balanced BST
N ≤ 1,000,000 → O(N) or O(N log N) single/two pass, sliding window
N ≤ 10^9      → O(log N) or O(√N)  binary search, math tricks

1. O(N log N) sort first → enables O(N) or O(log N) operations after
2. Two passes O(N) each = still O(N)
3. Nested loops with early break ≠ necessarily O(N²)
4. Recursion depth × work per call = space × time relationship
5. BFS uses O(W) space; DFS uses O(H) space — choose based on graph shape
6. HashMap insert/lookup = O(1) avg but O(N) worst — mention in interview
7. N + N/2 + N/4 + ... = 2N = O(N)  ← geometric series always converges!
8. Heapify = O(N),  building heap by N inserts = O(N log N)  ← different!