제4장 · 빅 오를 이용한 코드 속도 향상

§ 1 · 떠오르기버블 정렬의 절차

정렬 알고리즘은 모두 하나의 문제를 푼다 — "정렬되지 않은 숫자 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할까?" 버블 정렬(bubble sort)은 가장 기본적인 정렬 알고리즘이다.

Algorithm버블 정렬 — 4단계

① 비교 — 연속된 두 항목을 가리키고 비교한다.

② 교환 — 순서가 맞지 않으면(왼쪽 > 오른쪽) 둘을 교환한다.

③ 이동 — 포인터를 오른쪽으로 한 칸 옮긴다. 배열 끝까지 ①②를 반복한다.

④ 패스스루 반복 — 교환이 한 번도 없는 라운드가 나올 때까지 ①~③을 반복한다.

이름이 버블 정렬인 이유는, 각 패스스루(pass-through)마다 가장 큰 미정렬 값이 올바른 위치로 거품처럼 '떠오르기' 때문이다.

§ 2 · 한 단계씩버블 정렬 실행

배열 [4, 2, 7, 1, 3]을 버블 정렬로 정렬해 보자. 인접한 두 칸을 비교하고, 순서가 틀리면 교환한다. 각 패스스루가 끝날 때마다 가장 큰 값이 오른쪽 끝에 자리 잡는다.

모션 · 버블 정렬 [4, 2, 7, 1, 3] 단계 01 / 0

space 재생 · → 단계 · R 리셋

버블 정렬 — Python

def bubble_sort(list):
    unsorted_until_index = len(list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(unsorted_until_index):
            if list[i] > list[i+1]:
                sorted = False
                list[i], list[i+1] = list[i+1], list[i]
        unsorted_until_index = unsorted_until_index - 1

§ 3 · 이차 시간버블 정렬의 효율성

버블 정렬은 비교와 교환이라는 두 종류의 단계로 이루어진다. N개 요소에서 비교는 (N-1) + (N-2) + … + 1번이고, 최악의 경우 모든 비교마다 교환이 따른다.

버블 정렬의 단계 수는 대략 N²로 증가한다
N 데이터 요소	버블 정렬 단계 수	N²
5	20	25
10	90	100
20	380	400
80	6320	6400

이차 시간 — Quadratic Time

O(N²)

O(N²) — N개 데이터 요소에 대해 대략 N² 단계를 수행한다. 데이터가 늘수록 단계 수가 급격히 치솟는 상대적으로 비효율적인 알고리즘이다.

함정 중첩 루프를 볼 때마다 머릿속에서 O(N²) 경고음이 울려야 한다. 외부 루프가 N번, 그 안에서 내부 루프가 또 N번 — N × N = N² 단계다.

§ 4 · 중첩의 대가이차 시간 문제

배열에 중복 값이 있는지 확인하는 함수를 생각해 보자. 가장 먼저 떠오르는 접근은 중첩 for 루프다.

중복 검사 — 첫 번째 구현 O(N²) — JavaScript

function hasDuplicateValue(array) {
    for(var i = 0; i < array.length; i++) {
        for(var j = 0; j < array.length; j++) {
            if(i !== j && array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

모션 · 중첩 루프가 만드는 N² 비교 단계 01 / 0

space 재생 · → 단계 · R 리셋

§ 5 · O(N²) → O(N)선형 해결책

중첩 루프에 의존하지 않는 두 번째 구현이 있다. 만난 숫자를 보조 배열에 기록해 두고, 새 숫자를 만날 때마다 "이미 본 적 있나?"만 확인한다. 루프가 하나뿐이다.

중복 검사 — 두 번째 구현 O(N) — JavaScript

function hasDuplicateValue(array) {
    var existingNumbers = [];
    for(var i = 0; i < array.length; i++) {
        if(existingNumbers[array[i]] === undefined) {
            existingNumbers[array[i]] = 1;
        } else {
            return true;
        }
    }
    return false;
}

이 구현은 배열을 단 한 번 도므로 O(N)이다. hasDuplicateValue([1,2,3])은 3단계만 거친다 — 첫 구현이 9단계였던 것과 대조된다. 많은 데이터를 처리한다면 이 차이가 애플리케이션의 생사를 가른다.

핵심 느린 알고리즘을 만날 때마다 더 빠른 대안이 있는지 시간을 들여 생각해 보라. 항상 더 나은 길이 있는 것은 아니지만, 불가능하다고 결론짓기 전에 확인할 가치가 있다.

§ 6 · 정리이 장이 남긴 것

빅 오를 확실히 이해하면 느린 코드를 찾아내고 두 경쟁 알고리즘 중 빠른 것을 고를 수 있다. 그러나 빅 오가 두 알고리즘을 같은 등급으로 보지만 실제로는 하나가 더 빠른 경우도 있다. 다음 장에서 그 미세한 차이를 다룬다.

관련선택 정렬 — 상수 무시 관련해시 테이블로 중복 검사