연습 문제

복잡도 분석은 많이 읽고 직접 세어 볼수록 빨라집니다. 아래 다섯 문제는 차수 읽기, 더 나은 차수로 고치기, 측정으로 확인하기를 차례로 연습하도록 구성했습니다. 먼저 스스로 풀어 본 다음 접근 방법과 풀이를 확인하세요.

문제 1. 차수 맞히기

다음 네 함수의 시간 복잡도를 구하세요. c의 result는 리스트입니다.

def a(n):
    total, i = 0, 1
    while i < n:
        for _ in range(n):
            total += 1
        i *= 2
    return total

def b(n):
    total = 0
    for _ in range(n):
        j = 1
        while j * j <= n:
            total += 1
            j += 1
    return total

def c(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

def d(n):
    if n <= 1:
        return 1
    return d(n // 2) + d(n // 2)

접근: 바깥 반복과 안쪽 반복의 횟수를 따로 세어 곱합니다. 재귀는 점화식을 세웁니다.

• a: 바깥은 i가 두 배씩 커지므로 약 log n번, 안쪽은 n번입니다. O(n log n)
• b: 안쪽은 j ≤ √n까지 돌므로 O(n√n), 즉 O(n^1.5)
• c: x not in result가 리스트를 훑습니다. 모든 값이 다르면 0 + 1 + ... + (n-1)번 비교하므로 O(n²). 집합을 함께 쓰면 O(n)이 됩니다.
• d: T(n) = 2T(n/2) + O(1)이라 log n처럼 보이지만, 마스터 정리로 O(n)입니다. 호출 수를 세어 확인할 수 있습니다.

calls = 0

def d_counted(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return d_counted(n // 2) + d_counted(n // 2)

for n in (1_024, 2_048, 4_096):
    calls = 0
    d_counted(n)
    print(n, calls)   # 2047, 4095, 8191: n이 2배면 호출도 2배

문제 2. 처음 반복되는 값

리스트에서 두 번째로 나타나는 순간이 가장 이른 값을 돌려주세요. 없으면 None입니다. 예: [4, 7, 1, 7, 4]에서는 7이 먼저 두 번 나타나므로 답은 7입니다.

접근: 모든 쌍을 보면 O(n²)입니다. 앞에서부터 훑으며 본 값을 집합에 넣으면, 집합 조회가 평균 O(1)이므로 전체 O(n) 시간, O(n) 공간입니다.

def first_repeat(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_repeat([4, 7, 1, 7, 4]))  # 7
print(first_repeat([1, 2, 3]))        # None

메모리를 아껴야 하고 "중복이 있는가"만 알면 된다면, 정렬한 뒤 이웃끼리 비교하는 O(n log n) 시간 방법도 있습니다. 시간과 공간 중 무엇이 귀한지에 따라 고릅니다.

문제 3. 차이가 k인 쌍

오름차순으로 정렬된 정수 리스트와 0 이상의 정수 k가 주어질 때, 두 원소의 차가 정확히 k인 쌍이 있는지 판단하세요. O(n)으로 풀어야 합니다.

접근: 두 포인터 i < j를 둡니다. 차가 k보다 작으면 j를 늘려 차를 키우고, 크면 i를 늘려 차를 줄입니다. 두 포인터가 각각 최대 n번만 움직이므로 O(n)입니다.

def has_pair_with_difference(nums, k):
    i, j = 0, 1
    while j < len(nums):
        if i == j:
            j += 1
            continue
        diff = nums[j] - nums[i]
        if diff == k:
            return True
        if diff < k:
            j += 1
        else:
            i += 1
    return False

print(has_pair_with_difference([1, 3, 6, 10, 15], 4))  # True (6, 10)
print(has_pair_with_difference([1, 3, 6, 10, 15], 2))  # True (1, 3)
print(has_pair_with_difference([1, 3, 6, 10, 15], 8))  # False

문제 4. 구간 합 질의

길이 n인 리스트와 q개의 질의 (l, r)이 주어집니다. 각 질의마다 nums[l:r]의 합을 구하세요.

접근: 질의마다 sum(nums[l:r])을 하면 O(n·q)입니다. 누적 합 prefix[i] = nums[0] + ... + nums[i-1]을 한 번 만들어 두면 질의 하나가 뺄셈 한 번이 되어 전체 O(n + q)입니다.

from itertools import accumulate

def range_sums(nums, queries):
    prefix = [0, *accumulate(nums)]
    return [prefix[r] - prefix[l] for l, r in queries]

print(range_sums([3, 1, 4, 1, 5, 9], [(0, 3), (2, 6), (5, 6)]))  # [8, 19, 9]

문제 5. 측정으로 차수 추정하기

함수와 입력 생성 함수를 받아, n과 2n에서 걸린 시간의 비율로 차수의 지수를 추정하세요.

접근: T(n) ≈ c·n^k라면 T(2n) / T(n) ≈ 2^k이므로 k ≈ log₂(T(2n) / T(n))입니다. 잡음을 줄이려고 timeit.repeat의 최솟값을 씁니다.

import math
import timeit

def estimate_exponent(func, make_input, n, number=3):
    def best_time(size):
        data = make_input(size)
        return min(timeit.repeat(lambda: func(data), number=number, repeat=5))
    return math.log2(best_time(2 * n) / best_time(n))

def all_pairs(items):
    return sum(1 for i in range(len(items)) for j in range(i + 1, len(items)))

print(round(estimate_exponent(sum, lambda n: list(range(n)), 200_000), 1))   # 약 1
print(round(estimate_exponent(all_pairs, lambda n: list(range(n)), 1_000), 1))  # 약 2

정리

• 반복 횟수를 곱하고, 숨은 in list 비용과 재귀 점화식을 놓치지 않는 것이 차수 읽기의 핵심입니다.
• 집합, 두 포인터, 누적 합은 O(n²) 또는 O(n·q)를 선형으로 줄이는 대표 도구입니다.
• 이론으로 구한 차수는 두 배 실험으로 확인하는 습관을 들이면 좋습니다.