이 문서에 대하여

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

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

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

증가량 비교

그래프 비교

Graphs of functions commonly used in the analysis of algorithms

이미지 출처는 Big_O_notation(wikipedia)

주요 증가율

  • 위로 올라갈수록 증가폭이 크다.
  • 아래로 내려갈수록 증가폭이 작다.
시간 복잡도 한국어 명칭 영문 명칭
지수형 Exponential
3차형 Cubic
2차형 Quadratic
선형 로그형 Linear Logarithmic
선형 Linear
로그형 Logarithmic
1 상수형 Constant

다양한 증가율 비교

  • 위로 올라갈수록 증가폭이 크다.
  • 아래로 내려갈수록 증가폭이 작다.
시간 복잡도  
 
팩토리얼 증가.
지수 증가.
 
 
 
선형 증가.
 
 
 
상수. 증가하지 않는다.

예제로 이해하자

쉬운 예제

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

상한

헷갈리는 예제

안쪽 루프가 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 및 참고문헌