입력 크기·O·Ω·Θ와 정보의 개수

빠르다는 느낌은 입력이 커질 때 얼마나 빨리 늘어나는지 말해 주지 않습니다. 목표는 입력 크기를 지정하고 연산 횟수의 증가율을 읽는 것입니다. 반복 횟수와 2의 거듭제곱을 사용하지만 로그를 미리 배울 필요는 없습니다.

개념과 약속

n이 입력 원소 수일 때 O(f(n))는 충분히 큰 n에서 비용의 상한, Ω(f(n))는 하한, Θ(f(n))는 둘 다 성립하는 정확한 증가 규모입니다. 이 표기는 '최악/최선/평균' 자체와 같은 뜻이 아닙니다. 먼저 어떤 경우의 비용 함수인지 정한 뒤 상한과 하한을 말합니다. 순차 탐색 최악은 Θ(n), 첫 원소가 맞는 경우는 Θ(1)입니다.

선택 심화: '충분히 큰'을 상수로 확인하기

비용 함수 T(n)이 n≥n₀인 모든 입력 크기에서 T(n) ≤ C·g(n)을 만족하는 양의 상수 C와 시작점 n₀가 있으면 T(n)=O(g(n))입니다. C와 n₀는 한 번 정한 뒤 n에 따라 바꾸지 않습니다. Ω는 c·g(n) ≤ T(n)인 양의 c와 시작점이 있다는 뜻이며, 두 부등식을 함께 보이면 Θ입니다.

예를 들어 T(n)=3n+7, g(n)=n이라 합시다. n≥1이면 7≤7n이므로 3n+7 ≤ 3n+7n = 10n입니다. 따라서 C=10, n₀=1이 O(n)의 증거입니다. 또 모든 n≥1에서 3n ≤ 3n+7이므로 c=3이 Ω(n)의 증거입니다. 두 결과를 합쳐 Θ(n)입니다. 상수는 유일하지 않아 C=4, n₀=7도 상한 증거가 됩니다.

상수와 증가율은 함께 봐야 합니다. 5n과 n²는 n=4에서 20과 16이지만, n=6에서는 30과 36입니다. 두 값은 n=5에서 같고, 그 뒤 n²이 더 큽니다. 작은 입력의 측정 순서가 큰 입력의 증가율 순서를 대신하지 않습니다. 몇 개의 숫자를 실행한 결과만으로 '모든 n≥n₀'의 부등식을 증명할 수는 없습니다. 형식적 정의는 Cornell의 점근 분석 강의와 대조할 수 있습니다.

반복을 절반씩 줄이면 약 log₂ n 단계, 두 겹으로 n번씩 반복하면 약 n² 단계입니다. 이진 센서 k개는 각 센서의 0/1 상태 조합 2ᵏ개를 구별합니다. n개의 후보에 고유 코드를 주려면 2ᵏ ≥ n인 가장 작은 k가 필요합니다. 후보 하나는 구별할 다른 후보가 없어 비트 0개로 표현할 수 있습니다. 이 코드는 정보량의 모델이며 센서의 오차·물리 동작은 따로 설계해야 합니다. 함수는 (폭, 코드 목록) 두 값을 튜플로 함께 반환합니다. 튜플은 순서가 있는 변경 불가능한 값의 묶음입니다.

손으로 상태 추적하기

5개 후보는 000, 001, 010, 011, 100으로 구별합니다. 모든 조합을 꼭 사용해야 하는 것은 아닙니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

bit_length()는 정수의 이진 표현 자릿수입니다. format(index, ...)는 번호를 지정한 폭의 이진 문자열로 바꿉니다. f"0{width}b"에서 중괄호 안의 width가 문자열에 들어가고 b는 이진 표시입니다. 결과는 폭과 코드 목록을 한 묶음으로 반환합니다.

def sensor_codes(count):
    if count < 1:
        raise ValueError("positive item count required")
    width = (count - 1).bit_length()
    return width, [format(i, f"0{width}b") if width else "" for i in range(count)]


print(sensor_codes(5))
print(sensor_codes(1))
for n in [10, 100, 1000]:
    print(n, n, n * n)

실행 결과:

(3, ['000', '001', '010', '011', '100'])
(0, [''])
10 10 100
100 100 10000
1000 1000 1000000

왜 맞고 언제 끝나는가

코드의 폭 k는 (n-1).bit_length()로 구합니다. n-1을 이진수로 표현하는 데 필요한 자릿수가 0부터 n-1까지의 서로 다른 번호를 담는 최소 폭입니다. 정수마다 고유한 표현이므로 코드가 겹치지 않습니다. 범위 n개를 순회해 종료합니다.

비용과 적용 범위

센서 코드를 모두 출력하려면 n개의 문자열을 각각 k자리 만들어 Θ(nk) 크기를 씁니다. 센서 수 계산만 로그 규모라고 전체 코드 생성도 O(log n)인 것은 아닙니다. 일반 알고리즘 분석에서는 비교 가능한 작은 수를 한 단위로 보며, 매우 큰 정수와 문자열 비교 비용은 별도 표시합니다.

스스로 풀어 보기

1. 후보 9개에 비트 세 개로 충분한가요? 최소 비트 수를 구하세요.
2. O(n²)이라는 상한만 보고 실제 비용이 반드시 n²에 비례한다고 말할 수 있나요?

힌트

1. 세 비트는 여덟 조합입니다.
2. 선형 함수도 이차 함수의 상한 안에 들어갑니다.

해설

1. 충분하지 않으며 네 비트가 필요합니다. 2⁴=16이 9 이상인 첫 거듭제곱입니다.
2. 말할 수 없습니다. 정확한 규모를 나타내려면 Θ(n²)와 그 근거가 필요합니다. O 표기를 느슨한 상한으로 사용하는 경우를 구분하세요.

흔한 오해

O(1)은 실제로 1초라는 뜻이 아닙니다. 입력 크기에 따른 증가율일 뿐이며 상수·컴퓨터·언어·입출력에 따라 측정 시간이 달라집니다.

복습과 다음 연결

정렬 비교에서 같은 입력으로 증가율과 측정을 나란히 봅니다. 두 입력 길이가 있는 LCS는 n 하나로 합치지 않고 m과 n을 구분합니다.