1∃ c, n₀ > 0, 使得 0 ≤ f(n) ≤ c·g(n) 对所有 n ≥ n₀ 成立

1n=10         n=100
2O(1)        1 → 1
3O(log n)    ~3 → ~7
4O(n)        10 → 100
5O(n log n)  ~33 → ~664
6O(n²)       100 → 10,000
7O(2ⁿ)       1024 → 1.26e+30

1function getFirstElement(arr) {
2  return arr[0]; // 内存地址计算：base_address + index*sizeof(type)
3}

1T(n) = T(n/2) + O(1) → O(log n)

1T(n) = 2T(n/2) + O(n)
2根据主定理（Master Theorem），a=2, b=2 → Case 2 → O(n log n)

1def matrix_mult(A, B):
2    n = len(A)
3    result = [[0]*n for _ in range(n)]
4    for i in range(n):          # O(n)
5        for j in range(n):      # O(n)
6            for k in range(n):  # O(n)
7                result[i][j] += A[i][k] * B[k][j]
8    return result               # 总时间复杂度 O(n³)

1function reverseArray(arr) {
2  let left = 0;
3  let right = arr.length - 1;
4  while (left < right) {
5    [arr[left], arr[right]] = [arr[right], arr[left]]; // O(1) 额外空间
6    left++;
7    right--;
8  }
9  return arr;
10}

1function fibonacci(n) {
2  if (n <= 1) return n;
3  return fibonacci(n-1) + fibonacci(n-2); // 空间复杂度 O(n)
4}

1# 使用装饰器测量实际执行时间
2import time
3def timing_decorator(func):
4    def wrapper(*args, **kwargs):
5        start = time.perf_counter()
6        result = func(*args, **kwargs)
7        print(f"{func.__name__}耗时: {time.perf_counter()-start:.6f}s")
8        return result
9    return wrapper