Big O Notation: A-Level CS가 실제로 기대하는 것

Big O 표기법은 모든 주요 A-level 컴퓨터 과학 커리큘럼(AQA, OCR, Edexcel)에 나타나며, 많은 학생들을 막히게 하는 이유는 수학이 어려워서가 아니라 실제 코드와 연결되는 모습을 본 적이 없기 때문이다. 여기서는 알아야 할 것과 불필요한 설명 없이 시험 문제에 답하는 방법을 다룬다.

Big O가 실제로 측정하는 것

Big O는 입력 크기(보통 n이라고 부름)가 커질 때 알고리즘의 실행 시간(또는 메모리 사용량)이 어떻게 증가하는지 설명한다. 초 단위의 스톱워치 측정이 아니다. 하드웨어와 무관하게 알고리즘을 비교할 수 있도록 성장률을 설명하는 방식이다.

O(n)을 쓸 때, 입력을 두 배로 늘리면 작업량도 대략 두 배가 된다는 뜻이다. O(n²)는 입력을 두 배로 늘리면 작업량이 대략 4배가 된다는 의미다. 시험관들이 원하는 것은 정확한 연산 개수가 아니라 그 관계를 파악하는 것이다.

반드시 알아야 할 복잡도

A-level에서 반복적으로 나오는 것들은 다음과 같다:

• O(1) – 상수 시간. 배열 요소를 인덱스로 접근: arr[5]. 배열의 크기는 상관없다.
• O(log n) – 로그. 정렬된 리스트에서 이진 탐색. 각 단계마다 남은 탐색 공간을 절반으로 줄인다.
• O(n) – 선형. 리스트 전체를 한 번 반복, 예를 들어 각 항목을 한 번씩 확인하는 선형 탐색.
• O(n log n) – 선형 로그. 병합 정렬과 퀵 정렬(평균 경우)이 여기에 해당한다.
• O(n²) – 이차. 같은 데이터에 대한 중첩 루프인데, 이것이 정확히 버블 정렬, 삽입 정렬, 선택 정렬이 하는 것이다.
• O(2ⁿ) – 지수. 메모이제이션 없는 순진한 재귀 피보나치. 빠르게 복잡해진다.

의사 코드를 보고 이 중 어느 것인지 바로 말할 수 있어야 하는데, 대부분이 이 부분을 테스트하기 때문이다.

코드에서 복잡도 읽기

항상 작동하는 방법: 루프를 세고 그것이 n과 어떻게 관계되는지 본다.

# O(n) - 루프 하나, 한 번의 통과
for i in range(n):
    print(i)

# O(n^2) - 중첩 루프, 둘 다 n에 연결됨
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - 탐색 공간이 매 반복마다 절반이 됨
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

내부 루프의 범위가 n에 따라 달라지는 중첩 루프는 여전히 O(n²)인데, 보기에는 약간 다를 수 있다(for j in range(i) 대신 for j in range(n)처럼 — 여전히 이차이지만 상수 인수 차이가 있을 뿐이다).

n과 무관한 루프에 주의하라. 입력 크기와 상관없이 항상 10번 실행되는 루프는 O(1)인데, 루프가 있음에도 불구하고 말이다. 시험관들이 이런 것을 슬쩍 넣는 것을 좋아한다.

일반적인 정렬 알고리즘과 Big O

이것은 두 가지 스펙을 한 번에 결합하므로 좋아하는 시험 주제다: 정렬 알고리즘과 복잡도.

알고리즘	최선의 경우	최악의 경우
버블 정렬	O(n)	O(n²)
삽입 정렬	O(n)	O(n²)
병합 정렬	O(n log n)	O(n log n)
이진 탐색	O(1)	O(log n)
선형 탐색	O(1)	O(n)

병합 정렬의 일관성(최선과 최악의 경우가 같은 복잡도)은 대규모 데이터셋에서 버블 정렬 대신 왜 선택하는지를 묻는 문제에서 명시적으로 언급할 가치가 있다. 버블 정렬의 최선의 경우 O(n)은 한 번의 통과에서 스왑이 없을 때 조기 종료 최적화가 있을 때만 적용되므로, 이를 언급하면 도움이 된다. 일부 시험 위원회에서는 이를 기대하기 때문이다.

학생들이 점수를 잃는 부분

가장 큰 것: 작성