이 문서에 대하여

  • 종종 헷갈리곤 하는 정보를 기록한다.
  • 이 문서는 빅 오 표기법을 모르는 사람을 대상으로 삼지 않는다.

big-, big-, big-는 각각 상한, 하한, 딱 맞는 수행 시간을 의미한다.

  • big-
    • 빅-오 라고 읽는다.
    • 점근적 상한에 대한 표기법.
  • big-
    • 빅-오메가 라고 읽는다.
    • 점근적 하한에 대한 표기법.
  • big-
    • 빅-세타 라고 읽는다.

TAOCP도 찾아보자

TAOCP 1권의 1.2.11.1 O 표기법 챕터를 찾아보자.

Let’s look at some more examples. We know that

그럼 예들을 좀 더 보자. 다음은 우리가 알고 있는 것이다.

so it follows that

이로부터 다음을 얻는다.

Equation (2) is rather crude, but not incorrect; Eq. (3) is a stronger statement; and Eq. (4) is stronger yet.

식 (2)가 상당히 대략적이긴 하지만, 그렇다고 부정확한 것은 아니다. 식 (3)은 좀 더 엄정한 서술이다. 그리고 식 (4)는 더욱 엄정하다.

(중략)

The O-notation is a big help in approximation work, since it describes briefly a concept that occurs often and it suppresses detailed information that is usually irrelevant. Furthermore, it can be manipulated algebraically in familiar ways, although certain important differences need to be kept in mind. The most important consideration is the idea of one-way equalities: We write , but we never write . (Or else, since , we might come up with the absurd relation .) We always use the convention that the right-hand side of an equation does not give more information than the left-hand side; the right-hand side is a “crudification” of the left.

O 표기법은 자주 나타나는 개념을 간략히 서술하고 대체로 별 상관이 없는 세부 정보를 숨긴다는 점에서 근사를 다룰 때 큰 도움이 된다. 더 나아가서, 이 O들을 익숙한 대수적 방법으로 조작하는 것이 가능하다. 단, 몇 가지 중요한 차이들은 염두에 두어야 하는데, 가장 중요한 것이 단방향 상등(one-way equality)이라는 개념이다. 즉, 이라고 쓸 수는 있지만 이라고는 절대 쓸 수 없다. (만일 그런 표기가 허용된다면, 이므로 이라는 터무니없는 결과가 나온다.) 이 표기법이 관련된 등식에서는 항상 등식의 우변이 좌변보다 더 자세한 정보를 제공하지 않는다는 관례를 사용한다. 즉, 우변은 항상 좌변보다 조악한 버전인 것이다.

증가량 비교

그래프 비교

Graphs of functions commonly used in the analysis of algorithms

이미지 출처는 Big_O_notation(wikipedia)

주요 증가율

시간 복잡도 한국어 명칭 영문 명칭 이 두 배가 되면
상수 constant 변함없다
로그 logarithmic 약간의 상수만큼 커진다
선형 linear 2배 커진다
선형 로그형 linear logarithmic, n log n 2배보다 약간 커진다
2차형, 제곱배 quadratic 4배 커진다
3차형 cubic 8배 커진다
, (상수 ) k승배, 다항 polynomial 배 커진다
, (상수 ) 기하급수배 exponential 배 커진다
계승배 factorial 배 정도 커진다.

예제로 이해하자

쉬운 예제

상수항은 무시하고, 지배적이지 않은 항도 무시한다.

상한

헷갈리는 예제

안쪽 루프가 1씩 줄어드는 이중 루프

function test(list) {
    for (var i = 0; i < list.length; i++) {
        for (var j = 0; j < list.length; j++) {
            console.log(i + ',' + j);
        }
    }
}

위의 코드는 list를 이중으로 돌리고 있으므로 이다.

아래의 코드는 ji+1로 시작하므로 루프가 진행될수록 안쪽 루프의 횟수가 줄어든다.

좀 헷갈린다.

function test(list) {
    for (var i = 0; i < list.length; i++) {
        // j = i + 1 에 주목
        for (var j = i + 1; j < list.length; j++) {
            console.log(i + ',' + j);
        }
    }
}

그러나 반복 횟수를 다음과 같이 생각해 보면 임을 알 수 있다.

두 개의 다른 리스트를 루프하는 이중 루프

function test(listA, listB) {
    // 바깥쪽 루프는 listA
    for (var i = 0; i < listA.length; i++) {
        // 안쪽 루프는 listB
        for (var j = 0; j < listB.length; j++) {
            console.log(i + ',' + j);
        }
    }
}
  • 답은 .
    • 느낌상 일 것 같지만, 아니다.
    • 두 리스트의 길이가 같으리란 보장이 없다.
    • 두 리스트의 크기를 모두 고려해야 한다.

그렇다면 아래와 같은 삼중 루프는 어떻게 될까?

function test(listA, listB) {
    for (var i = 0; i < listA.length; i++) {
        for (var j = 0; j < listB.length; j++) {
            for (var k = 0; k < 99999; k++) {
                console.log(i + ',' + j + ',' + k);
            }
        }
    }
}
  • 답은 .
    • 당연히 99999는 무시한다.

문자열 배열 정렬 문제

이 문제의 출처는 코딩 인터뷰 완전 분석이다.

다음과 같은 알고리즘이 있다고 하자.

  • 여러 개의 문자열로 구성된 배열(String[])이 주어진다.
  • 각각의 문자열을 먼저 abc 순으로 정렬한다.
  • 배열(String[])을 정렬한다.

알고리즘의 수행 시간은?

  • 이 문제는 생각보다 까다롭다.
  • 얼핏 생각해보면 일 것 같지만 틀린 답이다.

제대로 풀어보면 다음과 같다.

  • 정의
    • 가장 길이가 긴 문자열의 길이를 s라 하자.
    • 배열의 길이를 a라 하자.
  • 문자열 정렬
    • 문자열 하나하나를 정렬하는데 소요.
    • 문자열은 모두 a개.
    • 즉, 모든 문자열 정렬에 소요.
  • 배열 정렬
    • 배열의 길이 : a
    • 문자열 두 개를 비교(최악의 경우) :
    • 정렬에 필요한 시간 :
    • 즉, 배열을 정렬하는 데에 소요.
  • 결론
    • .
    • 이보다 더 줄일 수는 없다.

Links 및 참고문헌