[코딩 테스트 대비] 코테 시간복잡도 계산

프로그램 구현 전에 시간복잡도를 미리 계산해봐야한다.

문제에서 주어지는 시간/메모리 제한을 벗어나는 지를 확인해봐야하기 때문이다.

 

 

* 탐색 횟수당 걸리는 시간

1억 (100,000,000 = 10^8 ) → 1초

10억 = 1,000,000,000 = 10^9 → 10초

 

예를 들어 int는 4byte로 -2,147,483,648~ 2,147,483,647 범위이기 때문에

크기로 보면 "21억"이며 for문으로 탐색한다면 21초가 소요된다.

 

 

* 시간 복잡도 Big-O(빅오) 크기 비교

O(1) < O(log n) < O(n) < O(n log n) < O(N^2) < O(2^n) < O(n!) < O(n^n)

 

 

* N=1억 이라고 했을 때, 빅오표기법에 따른 실행시간

즉, 실행시간이 1초로 제한되어 있다면 O(N)의 탐색문으로 끝나는지를 확인해봐야 한다.

 

 

* 실행시간을 측정하는 방법

1) time() 함수

#include <iostream>
#include <time.h>

int main() {
    int sum = 0;
    time_t start = time(NULL);
    
    for (int i = 0; i < 10000; i++)
        for (int j = 0; j < 10000; j++)
            sum += i * j;    
    
    time_t end = time(NULL);
    cout << "소요시간: ", << (double)(end - start));
}

 

2) clock() 함수

#include <iostream>
#include <time.h>

int main() {
    clock_t start = clock();
    
    int sum = 0;
    for (int i = 0; i < 10000; ++i)
        for(int j = 0; j < 10000; ++j)
            sum += 1;
    clock_t end = clock();
    cout << "소요 시간: " << (double)(end - start) / CLOCKS_PER_SEC);
}

=> 시작부분과 끝부분의 시간을 저장해서 뺌으로써 구할 수 있다.

 

 

* 구현법에 따른 빅오 계산

알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? (빅-오)