01. 빅오 표기법, 시간복잡도, 공간복잡도(1)

자료구조나 알고리즘에서 성능 측정의 가장 중요한 지표인데요. 바로 Big-O notation입니다.

 

 

정의가 상당히 아름다운데요. 번역하자면 n0 이상의 모든 n에 대해 f(n) <= cg(n). 갑자기 엡실론-델타 논법이 떠오르네요... 엄밀한 정의는 상당히 어렵다고 볼 수 있겠군요. 예시를 보면 사실 이해가 쉽습니다.(고등학교 수학이 그랬던 것처럼요. 엄밀한 정의보다 대표문제를 몇개 풀어보면 쉽게 이해가 되었죠...비록 그것이 완전한 이해가 아니여도요.)

 

n > O(n)

2n > O(n) : n0 = 1, c = 2로 두면 2n <= 2n이 되어 만족

 

이처럼 coeffiecient가 상관없다. 즉, 차수가 중요하다는 것을 알 수 있습니다. 갑자기 무한대의 종류나 Cardinality(집합의 크기 또는 농도) 개념이 떠오르네요. 무한히 다른 무한의 존재는 칸토어가 증명하였죠. 갑자기 이상한 곳으로 빠졌군요...

어쨋든 n^2과 n이 있으면 n^2이 커지는 정도가 n이 커지는 정도보다 크다. 즉, 영향력 차이가 존재한다라고 생각하시면 좋을 듯 합니다. 

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) ...

 

이게 왜 중요하냐? 간단한 문제를 풀어보죠. 1~N까지의 합을 구하는 간단한 문제입니다.

#include <stdio.h>

int main(){
    int N, sum = 0;
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        sum += i;
    printf("%d", sum);
    
    return 0;
}

 

자, 그럼 for문 한번 돌아가는데 i 증가 연산, sum에 i를 더하는 연산, i조건확인 연산 최소 3개의 연산이 필요하네요. 최소한 3N번의 연산을 하는 것으로 볼 수 있습니다. 빅오 표기법으로 나타내면 O(N)이겠네요.

 

여기서 굳이 이렇게 구해야 하나?라는 생각을 가지셨다면 고등학교 수학 기초가 잘 되어 있으신 분입니다.

#include <stdio.h>

int main(){
    int N, sum = 0;
    scanf("%d", &N);
    SUM = N*(N+1)/2;
    printf("%d", sum);
    
    return 0;
}

아주 간단하죠 곱셈과 나눗셈. O(1)이 됩니다.

 

N의 크기가 커진다면 엄청난 차이가 될 것입니다. 같은 문제라도 이처럼 어떻게 푸느냐에 따라 시간복잡도가 달라질 수 있습니다. 백준 온라인 저지에서 시간초과를 맛보신 분들이라면 아실거에요. 이 문제처럼 N의 조건이 만약 백만이라면 O(N) 알고리즘의 경우 백만번정도를 계산하게 되겠구나라고 짐작할 수 있습니다. O(1) 알고리즘이라면 N과 관계없이 거의 바로 계산할 수 있다는 것을 알 수 있죠.

 

이는 코딩테스트에서 시간제한이 있을 경우 입력이 가장 큰 케이스가 몇번 정도의 연산에 끝날 수 있는가를 예측할 수 있는 좋은 정보가 됩니다. 중요한 것은 for문안에서 연산의 수를 줄이는 것보다 nested for문의 수를 줄이는 것입니다. 즉, 계수보다는 차수를 줄이는 것이 문제를 해결할 좋은 전략이라는 것이죠. 물론 계수가 critical한 경우도 존재합니다. 숨겨진 계수가 너무 큰 경우이지요.(행렬 곱셈 알고리즘이 있을 수 있겠군요.)

 

사실 우리가 흔히 사용하는 O표기법은 Theta 표기법과 혼용하여 사용하는 경우가 많습니다.

 

 

시간복잡도 말고 공간복잡도가 있는데요. 시간복잡도는 실행시간을 측정했다면, 공간복잡도는 필요한 메모리와 관련있다고 생각하시면 됩니다. 

 

이번에도 예시를 살펴보는 것이 좋겠죠? 배열 A를 입력받아 그 중 X보다 작은 수만 원래 순서대로 출력하기.

#include <stdio.h>

int main(){
    int N, X, A[10000];
    scanf("%d %d", &N, &X);
    for(int i=0; i<N; i++)
        scanf("%d", A+i);
    for(int i=0; i<N; i++)
        if(A[i] < X) printf("%d", A[i]);
    return 0;
}

이런 방식이라면 일단 저장을 해야하니까 N개의 값을 저장해야하므로 O(N)입니다. 하지만 꼭 이런 방식으로 하지 않아도 되죠. 입력받자마자 처리하는 것입니다. 입력받자마자 무언가를 처리할 수 있을 때 미리 처리하는 것은 다른 문제를 풀때도 사용하면 좋을 때가 있습니다. 

#include <stdio.h>

int main(){
    int N, X, A;
    scanf("%d %d", &N, &X);
    for(int i=0; i<N; i++){
        scanf("%d", A);
        if(A < X) printf("%d", A);
	}
    return 0;
}

이러면 O(1)이 되고 말죠. N의 크기에 따라 첫번째 방식은 N에 비례해서 늘어나지만 두번째 방식은 N에 무관하게 상수의 갯수로 정해집니다. 물론 시간복잡도는 같죠.

 

공간복잡도는 시간복잡도에 우선순위가 밀리는 경우가 많습니다. 과거에는 메모리가 부족했지만 요즘은 그렇지 않으니까요. 하지만 연산속도는 한계가 있습니다. 물리적인 한계가 있기 때문이죠.(컴퓨터 구조 과목에서 배웠던 발열문제 등이 있을 겁니다.) 여러분이 메모리 초과보다는 시간 초과를 쉽게 마주칠 수 있는 이유죠.

 

 

Summary

Two kinds of efficiency

• Time efficiency, also called time complexity, indicates how fast an algorithm in question runs.
• Space efficiency, also called space complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and output.

 

 

How to measure an algorithm’s running time?

• One possible approach is to count the number of times the basic operation is executed.(identify the basic operation of the algorithm, and compute the number of times the basic operation is executed.)
• Basic operation: the operation contributing the most to the total running time. (usually the most time-consuming operation in the algorithm’s innermost loop)