复杂度分析指南 · 3/6

Implementation: Measuring Three Growth Rates

本章目前仅提供英文版。

We write O(n) linear search, O(log n) binary search and O(n²) pair counting in Python, time them with timeit, then port an O(n²) and an O(n) two-sum to C++, Java and TypeScript.

Python

import timeit

def linear_search(items, target):          # O(n)
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

def binary_search(items, target):          # O(log n), sorted input
    lo, hi = 0, len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(items) and items[lo] == target:
        return lo
    return -1

def count_pairs_with_sum(items, target):   # O(n²)
    count = 0
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] + items[j] == target:
                count += 1
    return count

linear_search scans from the front: worst case Θ(n).
binary_search keeps the range [lo, hi) and discards half of it per iteration, about log₂ n + 1 times. Then lo is the first index not less than the target (like bisect.bisect_left).
count_pairs_with_sum checks every pair i < j: n(n-1)/2 comparisons, Θ(n²).

Timing with timeit

timeit runs code many times with garbage collection off. Use repeat and keep the minimum; the rest is mostly noise.

def bench(func, *args, number=100, repeat=7):
    timer = timeit.Timer(lambda: func(*args))
    return min(timer.repeat(repeat=repeat, number=number)) / number

for n in (1_000, 2_000, 4_000):
    data = list(range(n))
    lin = bench(linear_search, data, -1)        # worst case
    bi = bench(binary_search, data, -1)
    pairs = bench(count_pairs_with_sum, data, -1, number=1, repeat=5)
    print(n, f"{lin:.2e} {bi:.2e} {pairs:.2e}")

Sample run:

n	Linear	Binary	Pairs
1,000	35.6 µs	0.78 µs	26.7 ms
2,000	75.7 µs	0.99 µs	115.2 ms
4,000	164.2 µs	0.91 µs	528.1 ms

Doubling n doubles linear search, quadruples pair counting, and binary search stays flat. This doubling experiment is the simplest check: a ratio of 2 means , 4 means , 8 means .

对本章有疑问？

n

n²

n³

def two_sum_quadratic(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None

def two_sum_linear(nums, target):
    seen = {}                        # value -> first index
    for j, x in enumerate(nums):
        i = seen.get(target - x)
        if i is not None:
            return i, j
        seen.setdefault(x, j)
    return None

nums = [8, 3, 11, 5, 2]
print(two_sum_quadratic(nums, 13), two_sum_linear(nums, 13))  # (0, 3) (0, 3)

#include <iostream>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

using Pair = std::optional<std::pair<int, int>>;

// O(n^2)
Pair twoSumQuadratic(const std::vector<int>& nums, int target) {
    for (std::size_t i = 0; i < nums.size(); ++i)
        for (std::size_t j = i + 1; j < nums.size(); ++j)
            if (nums[i] + nums[j] == target) return std::make_pair(int(i), int(j));
    return std::nullopt;
}

// O(n) average
Pair twoSumLinear(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // value -> first index
    for (std::size_t j = 0; j < nums.size(); ++j) {
        auto it = seen.find(target - nums[j]);
        if (it != seen.end()) return std::make_pair(it->second, int(j));
        seen.emplace(nums[j], int(j));
    }
    return std::nullopt;
}

int main() {
    if (auto r = twoSumLinear({8, 3, 11, 5, 2}, 13)) std::cout << r->first << ' ' << r->second << '\n';  // 0 3
}

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    // O(n^2)
    static int[] twoSumQuadratic(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] + nums[j] == target) return new int[] {i, j};
        return null;
    }

    // O(n) average
    static int[] twoSumLinear(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // value -> first index
        for (int j = 0; j < nums.length; j++) {
            Integer i = seen.get(target - nums[j]);
            if (i != null) return new int[] {i, j};
            seen.putIfAbsent(nums[j], j);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] r = twoSumLinear(new int[] {8, 3, 11, 5, 2}, 13);
        System.out.println(r[0] + " " + r[1]);  // 0 3
    }
}

// O(n^2)
function twoSumQuadratic(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return null;
}

// O(n) average
function twoSumLinear(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // value -> first index
  for (let j = 0; j < nums.length; j++) {
    const i = seen.get(target - nums[j]);
    if (i !== undefined) return [i, j];
    if (!seen.has(nums[j])) seen.set(nums[j], j);
  }
  return null;
}

const nums = [8, 3, 11, 5, 2];
console.log(twoSumQuadratic(nums, 13), twoSumLinear(nums, 13)); // [ 0, 3 ] [ 0, 3 ]