Big-O記法をゼロから学ぶ

アルゴリズムの効率を測る理由

# O(n) approach
def find_max_linear(nums):
    m = nums[0]
    for n in nums:
        if n > m: m = n
    return m

# O(n^2) approach (unnecessary double loop)
def find_max_quadratic(nums):
    for i in range(len(nums)):
        is_max = all(nums[i] >= nums[j] for j in range(len(nums)))
        if is_max: return nums[i]

print(find_max_linear([3, 1, 4, 1, 5, 9]))  # 9

Big-O：漸近的な上限

# T(n) = 3n^2 + 5n + 100 is O(n^2)
# because the n^2 term dominates for large n

# T(n) = 2n + 1000 is O(n)
# the constant 1000 becomes negligible

# Rule: drop constants and lower-order terms
# 5n^3 + 2n^2 + n + 1  =>  O(n^3)
# 100 * log(n) + n      =>  O(n)
print('O(n^2) example: counting iterations')
n = 1000
count = sum(1 for i in range(n) for j in range(n))
print(count)  # 1_000_000 = n^2

一般的な計算量クラス

import math

n = 1000
print(f'O(1):       {1}')
print(f'O(log n):   {int(math.log2(n))}')
print(f'O(n):       {n}')
print(f'O(n log n): {int(n * math.log2(n))}')
print(f'O(n^2):     {n**2}')
# O(2^n) for n=1000 is astronomically large
# O(n!) even larger

定数を省く: なぜ重要か

# Both are O(n) — different constants
def count_a(n):
    total = 0
    for i in range(n):   # n ops
        total += 1
    for i in range(n):   # n ops
        total += 1
    return total  # T(n) = 2n  =>  O(n)

def count_b(n):
    total = 0
    for i in range(5 * n):  # 5n ops
        total += 1
    return total  # T(n) = 5n  =>  O(n)

print(count_a(10), count_b(10))  # 20 50

最良ケース、平均ケース、最悪ケース

def linear_search(nums, target):
    for i, n in enumerate(nums):
        if n == target:
            return i  # best case: target at index 0 => O(1)
    return -1         # worst case: not found => O(n)

# Best case O(1): target is first element
print(linear_search([5,1,2,3], 5))   # 0

# Worst case O(n): target not in list
print(linear_search([1,2,3,4], 9))   # -1

O(log n): 探索範囲を半分にする

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid, steps
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

import math
arr = list(range(1000))
idx, s = binary_search(arr, 999)
print(f'Found at {idx} in {s} steps (log2(1000)~={math.log2(1000):.1f})')

O(n log n): ソートの下界

# Merge sort: O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: res.append(a[i]); i+=1
        else:             res.append(b[j]); j+=1
    return res + a[i:] + b[j:]

print(merge_sort([5,2,8,1,9,3]))  # [1,2,3,5,8,9]

償却計算量

# Dynamic array append is O(1) amortised
import sys

lst = []
capacities = []
for i in range(16):
    lst.append(i)
    capacities.append(sys.getsizeof(lst))

# Size jumps show reallocation events
for i, c in enumerate(capacities):
    if i > 0 and capacities[i] != capacities[i-1]:
        print(f'Realloc at i={i}, new size={c} bytes')

コードから計算量を見抜く

# Two independent passes: O(n) + O(n) = O(n)
def two_passes(nums):
    total = sum(nums)           # O(n)
    mean = total / len(nums)
    diffs = [abs(n - mean) for n in nums]  # O(n)
    return max(diffs)           # O(n)
# Overall: O(n) -- NOT O(n^2)

# Nested loops: O(n) * O(n) = O(n^2)
def all_pairs(nums):
    pairs = []
    for i in range(len(nums)):       # O(n)
        for j in range(i+1, len(nums)): # O(n)
            pairs.append((nums[i], nums[j]))
    return pairs  # O(n^2)

空間計算量の基礎

# O(1) space: reverse in-place
def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]
        l += 1; r -= 1

# O(n) space: create reversed copy
def reverse_copy(arr):
    return arr[::-1]

a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a)  # [5, 4, 3, 2, 1]

面接で計算量を説明する

# Example of explaining complexity step by step
def two_sum(nums, target):
    # O(n) time: one pass through nums
    # O(n) space: hash map stores up to n elements
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:   # O(1) lookup
            return [seen[complement], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

クイックチェック

レッスンの振り返り