티스토리 뷰

기본 이론

시간복잡도

RiKang 2018. 1. 17. 17:55

Table of Contents


개요

시간복잡도의 예시 : O(1), O(n), O(n^2)

O 표기법

실제 실행 시간




1. 개요


 깔끔하고 이해하기 쉬운 코드, 유지 보수하기 좋은 프로그램 구조 등등 좋은 프로그램의 조건에는 여러 가지가 있습니다. 하지만 이런 요소들은 프로그램을 개발하는 사람들의 기준이고, 프로그램을 사용하는 사람 입장에서 중요한 건 아닙니다.


 그렇다면 사용자의 입장에서 중요한 건 무엇일까요? 여기에도 다양한 답들이 존재할 수 있지만,  중 저희가 주목해야 할 요소로 프로그램의 실행 시간을 뽑을 수 있습니다. 예를 들어 검색에 3초가 걸리는 사이트와 0.1초가 걸리는 사이트가 있다고 했을 때, 사용자가 느끼는 답답함은 천지 차이일 것입니다. 따라서 프로그램을 만들 때도 실행 시간을 줄이기 위해 자료구조와 알고리즘을 동원하는 등 큰 노력을 하게 됩니다.


 하지만 실행 시간을 줄이는 방법을 배우기 이전에 알아야 할 것이 있습니다. 바로 실행 시간을 측정하는 방법입니다. 실행 시간을 측정한다고 하면, '실행 시간 0.1초.' 이런 식으로 초 단위를 재는 걸 생각해 볼 수 있습니다. 하지만 이렇게 직접적인 방법은 CPU의 성능, 운영체제, 사용한 언어 등에 따라 결과가 달라지기 때문에 사용되기 힘듭니다. 이 모든 요소를 하나하나 통일한다고 해도, 입력 데이터가 많을 때 빠른 프로그램과 적을 때 빠른 프로그램으로 나뉘는 등  다시 기준이 생기게 됩니다. 따라서 프로그램의 실행 시간을 측정하기 위한 다른 방식이 존재하고 있습니다. 바로 시간복잡도(time complexity) 입니다.




2. 시간복잡도의 예시 : O(1), O(n), O(n^2)


 우선 시간복잡도를 표시할 때 많이 사용하는 O 표기법(big o notation, 빅 o 표기법)의 예시를 통해 시간복잡도에 대한 감을 잡아보도록 하겠습니다. 대부분의 경우, O 표기법의 괄호 안에 적힌 식이 클수록 실행 시간이 오래 걸리게 됩니다.


O(1)


 항상 같은 수의 연산을 하는 프로그램은 시간복잡도 O(1)이 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//code by RiKang, weeklyps.com
//정수 2개를 입력받아 합을 출력하는 프로그램
//시간복잡도 O(1)
#include<stdio.h>
 
int main(){
    // a, b가 얼마가 들어오든 상관없이, Line 8 ~ 14 까지 총 7번의 연산을 합니다.
    int a;
    int b;
    scanf("%d",&a);
    scanf("%d",&b);
    a+=b;
    printf("%d\n",a);
    return 0;
}
cs


 위의 프로그램이 O(1)의 예시입니다. 어떤 입력이 들어오던지 항상 같은 수의 연산을 하게 됩니다.


O(n)


 입력 데이터가 n개일 때, 혹은 입력으로 n이 들어올 때, 상수 * n 번의 연산을 하는 프로그램은 시간복잡도 O(n)로 표기됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//code by RiKang, weeklyps.com
//1~n 자연수의 합을 출력
//시간복잡도 O(n)
#include<stdio.h>
 
int main(){
    // 3n+6 번의 연산을 수행합니다.
    int n;      // 1번
    int sum=0;  // 1번
    scanf("%d",&n); // 1번
    for(int i=1; i<=n; i++// for(1번, n번, n번)
        sum+=i; // n번
    printf("%d",sum); // 1번
    return 0// 1번
}
cs


 O(n)의 예시입니다. n과 비례한 3n+6번의 연산을 하는 걸 알 수 있습니다. 3n에 비하면 6번의 연산은 별로 중요하지 않기 때문에 3n번의 연산과 똑같이 O(n)로 표기됩니다. 그런데 사실, 이 프로그램은 더 효율적인 방법이 존재합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
//code by RiKang, weeklyps.com
//1~n 자연수의 합을 출력
//시간복잡도 O(1)
#include<stdio.h>
 
int main(){
    // 상수 번의 연산을 수행합니다.
    int n;
    scanf("%d",&n);
    int sum = n*(n+1)/2;
    printf("%d",sum);
    return 0;
}
cs


 수식을 이용해 합을 한 번에 계산하는 방법입니다. 이 방법은 항상 같은 수의 연산이 필요하고, 따라서 O(1)의 시간복잡도를 가지게 됩니다.


 이 프로그램과 위의 O(n) 프로그램을 비교해 보면 누가 보더라도 O(1) 프로그램이 효율적이고 빠를 것이라고 예상할 겁니다. n이 아주 작은 자연수가 아니라면 말이지요. 하지만 예상하는 것과 측정하는 것은 다른 영역입니다. 만약 아래의 프로그램이 더 빠른 걸 측정하겠다고 n=10일 때, n=100일 때, n=1000일 때 실행을 모두 실험해야 한다면 굉장히 번거로운 일이 될 것입니다. 하지만 우리에게는 이제 시간복잡도라는 무기가 있기 때문에 걱정할 것 없습니다. '아래의 프로그램은 O(1)이고 위의 프로그램은 O(n)이기 때문에 아래 것이 더 빠르다!' 라고 주장할 수 있기 때문입니다. 물론, 시간복잡도가 낮다고 해서 항상 빠른 것은 아니지만 입력의 크기가 커질수록 상대적으로 점점 더 빨라지게 된다는 건 알 수 있습니다.


O(n^2)


 입력 데이터가 n개일 때, 혹은 입력으로 n이 들어올 때, 상수 * n^2 번의 연산을 하는 프로그램은 시간복잡도 O(n^2)로 표기됩니다. ( n^2는를 간단히 표기한 것입니다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
//code by RiKang, weeklyps.com
//삼각형 모양의 별을 출력
//시간복잡도 O(n^2)
#include<stdio.h>
 
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++printf("\n"))
        for(int j=1; j<=i; j++)
            printf("*");
    return 0;
}
cs





3. O 표기법


 이제 시간복잡도(time complexity) 측정에 자주 사용되는 O 표기법(big o notation)에 대해 알아보겠습니다. O 표기법을 사용하면 프로그램의 실행 시간을 대략적인 함수로 나타낼 수 있습니다.


 연산 횟수를 나타내는 함수를 집어넣는 O 표기법에서는 가장 빠르게 증가하는 함수 이외의 함수들을 버리게 됩니다. 그리고 함수에 곱해지는 상수도 의미가 없으므로 버립니다. 예를 들면 번의 연산을 수행하는 프로그램의 시간복잡도가 이 되는 식이지요. 이처럼 O 표기법을 사용한 시간복잡도는 연산 횟수만 알면 쉽게 알아낼 수 있습니다.


 O 표기법 예시)



 하지만 시간복잡도를 완벽하게 계산해야 하거나, 증명해야 한다면 이런 간단한 계산법으론 부족합니다. 이럴 땐 O 표기법의 의미를 알아야 합니다.


 f(n) = O(g(n)) 의 의미는 다음과 같습니다.

 

인 모든 n에 대해 가 참이 되는 m과 C가 존재한다.


 예를 들어,  임을 증명하기 위해선 위의 명제가 참이 되는 m과 C를 찾아야 합니다. 넉넉하게 m=1, C=100으로 설정해 보겠습니다. 그럼 아래의 명제가 참임은 쉽게 증명할 수 있습니다.


인 모든 n에 대해 이다.


 명제를 참으로 만드는 m과 C를 찾았으므로 f(n)=O(n^2)가 됩니다. 따라서 프로그램이 실행하는 연산의 개수가 3n^2+n+1 일 때, 시간복잡도가 O(n^2)이라고 말할 수 있습니다.


 참고로 시간복잡도가 O(n)일 땐 선형 시간, O(n^2)의 다항식 꼴은 다항 시간, O(2^n) 같이 n이 지수에 들어가는 꼴은 지수 시간이 걸린다고 간단하게 이야기하기도 합니다.




4. 실제 실행 시간


 실제 실행 시간은 시간복잡도만 가지고 정확히 예측하기 힘듭니다. 같은 O(n)의 시간복잡도라도 100*n 번의 연산 수행과 10*n 번의 연산 수행은 엄연히 다르지요. 거기에 * 연산, + 연산, >> 연산에 필요한 실제 실행 시간도 모두 차이가 있고, 게다가 개요에서 설명했듯이 CPU의 성능, 언어, 컴파일러, 운영체제 등 많은 요소도 관여하게 됩니다.


 하지만 이런 조건들을 한정 지으면 대략적인 예측 정도는 가능하게 됩니다. 여기에서는 프로그래밍 언어 공부, 학교 시험, 코딩 테스트, 혹은 프로그래밍 대회에서 사용되는 일반적인 상황을 가정해보겠습니다. 이런 상황에선 가정, 학교에서 많이 쓰이는 PC나 노트북을 사용하게 됩니다. 여기에 사용되는 CPU와 컴파일러들은 1초에 수억 번의 연산을 수행할 수 있는 것으로 알려져 있습니다. 따라서 n=10000일 때, O(n^2) 프로그램을 실행시킨다면 '음, 대략 1,2초 정도 걸리겠군.'이라고 생각해 볼 수 있습니다. 그리고 1초 안에 실행이 끝나야 하는 프로그램을 설계할 때, n=100,000 인 상황에서 O(n^2) 의 프로그램을 설계하였다면, '시간복잡도가 너무 높으므로 다시 한번 생각해 봐야겠다.'는 틀을 잡을 수 있습니다.


실행 시간 제한

n의 최대 크기

시간복잡도 예시

1초

10,000,000

O(1), O(log n), O(n)

1초

1,000,000

O(n log n)

1초

100,000

O(n (log n)^2), O(n sqrt(n)) 

1초

5000

O(n^2)

1초

500

O(n^3), O(n^2 log n)

1초

20

O(2^n), O(n (2^n))

1초

10

O(n!)


 위의 표는 프로그램 실행 시간의 상항선(1초)과 n의 최대 크기가 주어졌을 때 사용되는 시간복잡도의 예시입니다. 물론 이 표는 참고 사항일 뿐이며, 이외에도 다양한 시간복잡도가 존재할 수 있고 같은 시간복잡도라도 연산이 더 많을수록 오래 걸린다는 점은 기억해야 합니다.

'기본 이론' 카테고리의 다른 글

자료구조  (0) 2018.01.20
시간복잡도  (0) 2018.01.17