[알고리즘] 시간 복잡도

• 알고리즘은 시간 복잡도와 공간 복잡도로 평가한다.
• 시간 복잡도는 알고리즘을 수행하는 데에 걸리는 시간, 공간 복잡도는 사용되는 메모리양에 해당한다.

빅오표기법(Big O)

표기	시간	설명	예시
O(1)	상수 시간	문제 해결에 오직 한번의 시간만 소요됨	스택의 Push, Pop
O(log N)	로그 시간	문제 해결에 필요한 단계가 특정 요인에 따라 줄어듦	이진 트리
O(N)	선형 시간	문제 해결에 N번의 단계가 필요함	한 단계의 반복문
O(N²)	이차 시간	N을 제곱한 단계가 필요함	퀵 정렬, 병합정렬, 힙 정렬
O(2ⁿ)	지수 시간	문제 조건에서 주어지는 상수의 n 제곱 단계가 소요됨	피보나치 수열

N에 따른 시간 복잡도 비교

Big O 표기	1	10	100
O(1)	1	1	1
O(log N)	0	1	2
O(N)	1	10	100
O(N²)	1	100	10000
O(2ⁿ)	2	1024	1.2676506e+30

N이 작을 때의 시간복잡도는 나열된 순서대로 커지지 않는다. 위에서 보는 것처럼 O(N)이 O(N²)보다 클 수 있다.
이렇게 N이 작다면 성능에 전혀 영향이 없다. N이 클 때, 최악의 경우를 계산하는 것이 중요하다. N이 커질수록 시간복잡도는 기하급수적으로 커진다.
N이 충분히 크고 필요한 연산이 30N, 혹은 503N² + N 등의 식이라고 가정할 때, 연산에 가장 큰 영향을 미치는 N을 빅오표기법으로 표현한다.

시간복잡도 비교 그래프

시간 복잡도 그래프

예제

O(1)

1부터 N까지의 합을 구하는 식. 가우스 공식을 이용하면 N의 값과 상관없이 1번의 연산으로 계산이 가능하다.

int n = 10;
int sum = (n+1)*n/2;

O(N)

위와 같이 1부터 N까지의 합을 구하는 식. 반복문을 이용해 i가 n과 같을 때까지 계산하므로 n번 연산해야한다.

int n = 10;
int sum = 0;
for(int i=1; i<=n; i++) {
    sum += i;
}

O(logN)

이진탐색은 정렬이 된 배열의 중간값을 찾으려는 값과 비교하면서 탐색 범위를 계속 반으로 좁혀간다.

static int searchRecursion(int[] numbers, int firstIdx, int lastIdx, int target) { 
    if(firstIdx > lastIdx) {
        return -1;
    }

    int middleIdx = (firstIdx + lastIdx) / 2;

    if(numbers[middleIdx] > target) {
        return searchRecursion(numbers, firstIdx, middleIdx -1, target);
    }else if(numbers[middleIdx] < target) {
        return searchRecursion(numbers, middleIdx + 1, lastIdx, target);
    }else {
        return middleIdx;
    }

}

이진탐색 자세히 알아보기 (12teamtoday.tistory.com/105)

[알고리즘] 이진탐색