[알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기

시간 복잡도 계산해보기

프로그램 작성 전에 어느정도 Input Data의 범위와 Logic 시간 복잡도로

수행 시간을 어림짐작할 수 있어야 합니다.

 

 

SW 알고리즘 문제에서는 크게 시간 / 공간 제한이 존재합니다.

※ 대부분 알고리즘 문제를 풀 때는 메모리 제한이 엄격하기 보다는

    시간 복잡도에서 주의해야 할 부분이 많으므로 이에 대해 다루고자 합니다.

※ 해당 글에서는 Big-O (빅오) 계산법을 중점으로 작성하였습니다.

 

 

Big-O 계산

Big-O 계산은 쉽게 큰 수치가 시간 복잡도를 크게 좌우한다고 보면 된다.

ex) N2 + N  → O(N2)

      N3  + N2 + N + 1 → O(N3)

최고 차항만 차수만을 표기,

다항식에서 작은 단위의 계수들이 아무리 커도 최고차항의 계수에 큰 영향 X

 

 

▶ 1억 (100,000,000 = 108 ) → 1초

    10억 = 1,000,000,000 = 109 (콤마(,)가 3개 있는 수치)

 

참고로 int는 4byte로 -2,147,483,648~ 2,147,483,647 범위이며,

(only 양수) 크기로 보면 "21억"이며

for문으로 탐색한다면 21초 소요되는 것을 어림짐작 할 수 있다.

 

 

시간 복잡도는 일반적으로 아래의 값으로 표현되는 경우가 많다.

▶ O(1) < O(log n) < O(n) < O(n log n) < O(N2) < O(2n) < O(n!) < O(nn)

 

📌 정렬 알고리즘 비교

정렬 알고리즘 비교

 

 

※ N = 1억이라고 했을 때, 실행시간은 아래와 같다.

 

예시 코드

void probing(){
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            ...
}

이중 for문으로 N = 10,000인 경우

한 번의 probing에 1초가 소요된다.

 

만약에 probing()이 10번 호출된다면

1초 × 10번 = 10초가 소요될 것이다.

 

 

지금까지 (Big-O) 시간 복잡도 계산하는 방법을 다루었지만 이 시간 계산이 절대적이지는 않다.

제출 서버 성능, CPU 성능, 연산 처리에 따라 다를 수 있기에 어림잡은 시간으로 여겨야 된다.

- 실제 주어지는 Input Data 특성

- 반복문 내부 분기 조건(순서)

- 메모리 사용 패턴

- 컴파일러 버전

 

Reference

- [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

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

- [C/C++] time(), clock()으로 실행시간 측정