2 / 16강

연산량으로 비교하기

같은 컴퓨터에서도 실행 시간은 입력이나 주변 작업에 따라 달라집니다. 먼저 입력이 커질 때 연산 횟수가 어떻게 늘어나는지 비교하면 알고리즘의 차이가 드러납니다.

모든 두 사람을 짝지으면

서로 다른 두 항목의 쌍을 한 번씩 만들겠습니다. A-B와 B-A는 같은 쌍으로 셉니다.

def count_pairs(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            count += 1
    return count

print(count_pairs(5))

결과는 10입니다. 첫 항목은 나머지 4개, 다음은 3개, 그다음은 2개와 1개를 만납니다. 총횟수는 4 + 3 + 2 + 1 = 10입니다. 일반적으로 n(n-1)/2번이므로 시간은 O(n²)입니다.

반복문 모양만 세면 안 됩니다

• 반복문이 두 개라도 하나가 끝난 뒤 다른 하나가 시작하면 n + n일 수 있습니다. 이때는 O(n)입니다.
• 안쪽 반복 횟수가 매번 절반으로 줄어들면 단순히 n을 곱할 수 없습니다.
• 호출한 함수 안에서 정렬이나 복사가 일어나는지도 확인해야 합니다.

빅 오 O는 증가율의 상한, 오메가 Ω는 하한, 세타 Θ는 양쪽이 같은 차수로 맞는 경우를 뜻합니다. 최선, 평균, 최악의 경우와는 별개의 구분입니다. 최악의 비용에도 상한과 하한이 있습니다.

시간과 공간은 다른 비용입니다

위 코드는 쌍을 저장하지 않고 개수만 셉니다. 추가 저장 공간은 고정된 변수 몇 개이므로 O(1)입니다. 모든 쌍을 목록에 담으면 시간뿐 아니라 출력 공간도 O(n²)이 됩니다.

이 강좌의 기본 분석에서는 숫자 하나의 비교나 덧셈을 일정 비용으로 봅니다. 매우 큰 정수나 긴 문자열을 다루면 값의 길이도 고려해야 합니다.

확인 문제

입력 크기를 1,000에서 2,000으로 늘리면 n²에 비례하는 작업은 대략 몇 배가 될까요? O(n)이 항상 실제로 더 빠르다는 뜻일까요?