알고리즘과 시간 복잡도

알고리즘(algorithm)은 문제를 푸는 절차를 순서대로 적은 것이고, 시간 복잡도(time complexity)는 입력 크기 n이 커질 때 그 절차가 거치는 단계 수가 얼마나 빨리 늘어나는지를 나타낸 것입니다. 같은 일을 하는 알고리즘도 데이터가 열 개일 때는 차이가 없다가 백만 개가 되면 몇 초와 몇 시간으로 갈립니다. 걸린 초는 컴퓨터마다 달라 견줄 수 없으니, 단계 수가 자라는 꼴을 빅오(Big-O) 표기로 적어 견줍니다. 아래 그림은 데이터 8칸에서 다섯 가지 일의 단계 수를 세고, n을 16과 32로 늘리며 그 수가 어떻게 벌어지는지 보여 줍니다.

1초 대신 단계 수를 센다

시간 복잡도는 견주기·옮기기 같은 기본 연산을 몇 번 하는지로 잽니다. 같은 n이라도 데이터가 놓인 모양에 따라 단계 수가 달라지므로, 보통 가장 오래 걸리는 경우(최악의 경우)로 적습니다. 앞에서부터 하나씩 견주는 탐색은 찾는 값이 맨 끝에 있으면 n번 견줍니다.

단계 수 대신 더 쓰는 기억 공간이 n에 따라 얼마나 늘어나는지는 공간 복잡도(space complexity)라고 합니다.

2대표적인 다섯 꼴

반복의 모양을 보면 꼴이 정해집니다. log n은 n을 2로 몇 번 나눠야 1이 되는지입니다(log₂ 8 = 3).

예에 든 정렬과 탐색은 이 단원의 선택·버블·삽입 정렬부터 차례로 배웁니다.

3가장 빨리 자라는 항만 남긴다

n이 8에서 32로 4배가 되는 동안 O(log n)은 3에서 5로, O(n)은 4배, O(n²)은 16배인 1024가 됩니다. n이 1 늘 때마다 2배가 되는 O(2ⁿ)(지수형)은 n이 32면 약 43억입니다. 꼴은 O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 차례로 빨리 자랍니다.

단계 수를 3n² + 5n + 2로 세었다면 n이 32일 때 3n² 항이 95%를, n이 1000이면 99.8%를 차지합니다. 그래서 계수와 작은 항을 버리고 O(n²)으로 적습니다. 3n²과 n²은 같은 꼴이라 둘 다 O(n²)입니다.

예제

반복 세 가지가 n = 16일 때 몇 번 도는지 세는 C 코드입니다. 찍힐 수를 먼저 짐작해 보세요.

#include <stdio.h>

int main(void) {
    int n = 16, i, j;
    int a = 0, b = 0, c = 0;
    for (i = 0; i < n; i++)
        a++;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            b++;
    for (i = n; i > 1; i /= 2)
        c++;
    printf("%d %d %d", a, b, c);
    return 0;
}

16 256 4

n을 32로 늘리면 32 1024 5가 찍힙니다. 그림에서 n = 32 열의 세 수와 같습니다.

시험 포인트

• 필기(시험에서는 1과목): 꼴을 빨리 자라는 차례로 늘어놓거나, O(1)이 '입력 크기와 상관없이 단계 수가 일정하다'는 뜻임을 고르게 합니다. 정렬·탐색과 복잡도를 짝지어 묻습니다 — 순차 탐색 O(n), 이진 탐색 O(log n), 선택·버블·삽입 정렬 O(n²), 퀵 정렬 평균 O(n log n)·최악 O(n²), 병합·힙 정렬 O(n log n).
• 실기: 이름을 한글 이름과 영문으로 씁니다 — 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity), 빅오 표기법(Big-O Notation).

확인 문제

1. 시간 복잡도가 O(n²)인 일을 고르세요. n은 사람 수나 종이 장수입니다.

• ① 사물함 번호를 듣고 그 칸을 바로 엽니다.
• ② 가나다순 명단의 가운데를 펴 보고, 찾는 이름이 없는 쪽 반을 버리기를 되풀이합니다.
• ③ 시험지 n장을 한 장씩 채점합니다.
• ④ n명이 서로 한 번씩 모두 악수합니다.

2. (가)~(다)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 정렬 A는 데이터 n개를 정리하는 동안 n²번쯤, 정렬 B는 n log n번쯤 견줍니다. 이처럼 입력이 커질 때 거치는 단계 수가 늘어나는 정도
• (나) 정렬 C는 데이터만큼의 칸을 따로 빌려 쓰고, 정렬 D는 몇 칸만 더 씁니다. 이처럼 입력이 커질 때 더 쓰는 메모리가 늘어나는 정도
• (다) 센 단계 수 4n² + 7n에서 가장 빨리 자라는 항만 남기고 계수 4를 버려 O(n²)으로 적는 방법

3. 예제 코드의 int n = 16을 int n = 64로 바꾸면 무엇이 찍힐까요? 답을 끝까지 쓴 뒤 정답을 펼치세요.