算法复杂度：渐进分析

大 O、大 Ω、大 Θ

- f(n) = O(g(n))：存在 c, n₀，使 f(n) ≤ c·g(n)，n ≥ n₀（上界） - f(n) = Ω(g(n))：下界 - f(n) = Θ(g(n))：上界且下界，精确渐进 工程中说「复杂度是 O(n log n)」通常指 Θ(n log n)——上下界都卡住了。

package main

import (
    "fmt"
    "sort"
    "time"
)

// O(n²) 冒泡排序 vs O(n log n) 标准库排序
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

func benchmark(n int) {
    data1 := make([]int, n)
    data2 := make([]int, n)
    for i := range data1 {
        data1[i] = n - i
        data2[i] = n - i
    }

    t1 := time.Now()
    if n <= 10000 {
        bubbleSort(data1)
    }
    d1 := time.Since(t1)

    t2 := time.Now()
    sort.Ints(data2)
    d2 := time.Since(t2)

    if n <= 10000 {
        fmt.Printf("n=%6d: 冒泡=%v 快排=%v 比值=%.0fx\n",
            n, d1, d2, float64(d1)/float64(d2))
    } else {
        fmt.Printf("n=%6d: 快排=%v（冒泡跳过，太慢）\n", n, d2)
    }
}

func main() {
    for _, n := range []int{1000, 5000, 10000, 100000, 1000000} {
        benchmark(n)
    }
}

主定理：推导分治算法的复杂度

形如 T(n) = aT(n/b) + f(n) 的递推关系（a 个规模 n/b 的子问题，每层合并代价 f(n)），主定理给出三种情况： 1. f(n) = O(n^{log_b a - ε})：合并代价被子问题主导，T(n) = Θ(n^{log_b a}) 2. f(n) = Θ(n^{log_b a})：同阶，T(n) = Θ(n^{log_b a} log n) 3. f(n) = Ω(n^{log_b a + ε})：合并代价主导，T(n) = Θ(f(n))

摊还分析：动态数组的 O(1) 均摊

动态数组（Go 的 slice）每次扩容复制所有元素，代价 O(n)。但每次追加是 O(1)。摊还分析证明：n 次追加的总代价是 O(n)，均摊每次 O(1)。分析技巧：势能函数法——把扩容的代价「借给」之前的 O(1) 操作分摊还清。

package main

import "fmt"

// 手动实现动态数组，观察扩容时机
type DynArray struct {
    data     []int
    size     int
    copyOps  int  // 记录总复制操作数
}

func (d *DynArray) Append(v int) {
    if d.size == len(d.data) {
        // 扩容：容量翻倍
        newData := make([]int, max(1, len(d.data)*2))
        copy(newData, d.data)
        d.copyOps += d.size  // 记录这次扩容的代价
        d.data = newData
    }
    d.data[d.size] = v
    d.size++
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

func main() {
    d := &DynArray{}
    n := 1024
    for i := 0; i < n; i++ {
        d.Append(i)
    }
    fmt.Printf("追加 %d 次，总复制操作: %d，均摊: %.1f 次/追加\n",
        n, d.copyOps, float64(d.copyOps)/float64(n))
    // 追加 1024 次，总复制操作: 1023，均摊: ~1.0 次/追加
}

O 记号是工程师的望远镜——它让你看到算法在无限大时的形状。

— 算法导论