복잡도 분석

complexity.py

import timeit


def two_sum_quadratic(nums, target):
    """O(n^2): try every pair."""
    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):
    """O(n) on average: remember values already seen."""
    seen = {}
    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


print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))

for n in (500, 1_000, 2_000):
    nums = list(range(0, 2 * n, 2))  # even numbers only, so no pair sums to -1
    slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
    fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
    print(f"n={n:>5}  O(n^2) {slow * 1000:8.2f} ms   O(n) {fast * 1000:6.3f} ms")

python complexity.py