시간 복잡도란?

시간 복잡도란?

• 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다.
• 시간 복잡도는 낮으면 낮을수록 좋다.

 

예시

만약 1차원 배열에 값이 들어가 있고, 특정 값을 배열의 맨 앞에서 순서대로 검색한다면 연산 횟수가 가장 적을 때와 가장 많을 때는?

 

연산 횟수가 가장 적은 경우

• 다음 그림과 같이 찾는 값이 검색 시작 위치에 바로 있는 경우이다.

 

연산 횟수가 가장 많은 경우

• 찾으려는 값이 아에 없거나 가장 마지막에 위치한 경우이다.

이러한 경우 시간 복잡도는 연산 횟수가 가장 적은 경우 시간 복잡도가 낮다라고 표현할 수 있다.

 

 

 

빅오 표기법

• 점근적 표기법인 상한선을 활용하여 시간 복잡도를 표기하는 방법이다.
• 어떤 프로그램 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(..)와 같이 표기하면 된다.

수식	빅오 표기	설명
3x² + 5x + 6	O(x²)	다항함수로 구성되어 있고, 최고차항 x²만 남는다.
x + logx	O(x)	다항함수와 로그함수로 구성되어 있으므로 증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남는다.
2x + 10x5 + 5x2	O(2x)	지수함수는 다항 함수보다 빠르게 증가하므로 지수 함수만 남는다.

 

 

다항 함수와 로그 함수 증가 폭 차이

 

 

 

 

지수 함수와 다항 함수 증가 폭 차이

 

 

 

왜 빅오 표기법은 증가 폭 차이에 따라 저렇게 표현하는 것일까?

• 아래 코드는 각각 n², n + 2n, 5번의 증가 연산을 한다.
• 즉 f(x) = x² + 3x + 5

function solution(n) {
    let count = 0;
    // 반복문 n²번 연산 수행
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            count += 1;
        }
    }
    // 반복문 n번 연산 수행
    for(let k = 0; k < n; k++) {
        count += 1;
    }
	// 반복문 2n번 연산 수행
    for(let i = 0; i < 2 * n; i++) {
        count += 1;
    }
	// 반복문 5번 연산 수행
    for(let i = 0; i < 5; i++) {
        count += 1;
    }

    console.log(count);
}

solution(6);

 

 

 

• 그래프를 보면 x=4일 때 f(x)를 넘으므로 2x²가 해당 공식을 만족한다.

 

 

 

• y = 50x일 경우도 만족할 수 있다.
• 그러나 x = 47일 때 다시 역전되기 때문에 f(x) = x² + 3x + 5의 시간 복잡도는 O(x²)이다.