알고리즘의 효율 분석

시간 복잡도란?

코딩 테스트에서 보게 되는 문제들은 저마다 "가장 효율적으로 해결할 수 있는 알고리즘"이 있습니다. 이러한 알고리즘은 시간 복잡도를 기준으로 선정해야 합니다.

시간 복잡도(time complexity)란 알고리즘의 성능을 나타내는 지표입니다. 입력 크기에 대한 연산 횟수의 상한을 의미합니다.

이러한 시간 복잡도는 낮을수록 가장 좋은 알고리즘입니다.

예를 들어 , , 가 있을 경우 앞에서부터 시간 복잡도가 낮다고 할 수 있습니다.

1차원 배열 검사하기

아래와 같은 배열이 있다고 하겠습니다.

const array = ["z", "e", "r", "o"];

연산 횟수가 가장 적은 경우

만약 우리가 z를 찾는다면 우리는 첫번째 인덱스에서 바로 찾을 수 있습니다.

첫번째 인덱스에 있으므로 1번의 검색을 통해 바로 찾을 수 있습니다.

/*
const array = ["z", "e", "r", "o"];
*/

console.log(array[0]); // "z"

연산 횟수가 가장 많은 경우

연산 횟수가 가장 많은 경우 값이 없거나 가장 마지막에 위치하는 경우입니다.

h를 찾을 경우 해당 문자는 배열에서 찾을 수 없습니다. 하지만 프로그램은 모릅니다. 때문에 모든 배열을 순회를 하고 나서야 없다는 것을 인지할 수 있습니다.

이럴 경우 마지막까지 순회를 해야하므로 배열의 길이가 n이라면 n번 탐색하게 되는 것입니다.

알고리즘 수행 시간을 측정하는 방법

절대 시간을 측정하는 방법

절대 시간을 측정하는 방법은 프로그램을 실행하여 프로그램이 걸리는 시간을 측정하면 됩니다. 이는 실행하는 환경에 따라 달라질 수 있어서 코딩 테스트에서 사용하지 않습니다.

시간 복잡도를 측정하는 방법

시간 복잡도를 측정하는 방법은 앞서 언급했던 '연산 횟수'와 관련이 있습니다. 최선(best), 보통(normal), 최악(worst)로 나눌 수 있으며 앞선 예제의 경우 최선의 경우 1번, 최악의 연산 횟수는 배열의 길이인 4번임을 알 수 있습니다.

시간 복잡도를 표현할 방법이 있습니다.

최선 1, 최악 8과 같이 이를 이야기하는 것은 말 그대로 쉽지 않습니다. 만약 배열의 크기가 1의 경우 최선, 최악 전부 1로 나타낼 수 있습니다. 이러한 경우는 특이 케이스로 그렇다고 해서 맨 앞 요소부터 하나씩 검사하기라고 단정짓기는 어렵습니다.

따라서 우리는 알고리즘 성능을 측정할 때 두 가지가 중요합니다.

첫 째, 최악의 경우를 고려한다.

앞서 예시를 통해 배열의 맨 앞에 있다고 1번만에 찾는건 매우 이상적인 상황입니다. 하지만 실제로는 그러지 않습니다. 왜냐하면 최선의 경우에서 측정하였기 때문입니다. 만약 없거나, 맨 마지막에 위치하고 있을 경우 우리는 n번을 모두 순회해서 알아보아야 합니다. 때문에 이러한 시간 복잡도를 나타낼 때는 최악의 경우를 고려하여 계산합니다.

둘 째, 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용한다.

코딩 테스트를 통해 알고 싶은 것은 정확한 연산 횟수가 아닌 제한 시간 내에 수행될 수 있을지 정도의 검사를 하는 것입니다. 따라서 정확한 연산 횟수가 아닌 연산 횟수의 추이를 활용하여 계산합니다.

예를 들어 배차 간격이 10분인 지하철을 탄다고 했을 때 우리는 "지하철을 10분안에는 탈 수 있다." 라고 카테고리화 할 수 있습니다. 코딩 테스트에서도 이와 같이 연산 횟수의 추이만 알고 있어도 성능을 충분히 가늠할 수 있고, 정확한 연산 횟수를 구할 때보다 더 빠르다는 장점도 있습니다.

그리고 코딩 테스트에서는 모든 경우의 수에서 알고리즘 문제를 처리하는 것을 고려해야 하므로 최악의 경우를 토대로 이야기하는 것이 일반적입니다.

최악의 경우 시간 복잡도를 표현하는 빅오 표기법

최악의 경우를 표현하는 방법을 우리는 빅오 표기법이라고 얘기합니다. 프로그램의 연산 횟수가 라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(...)으로 표기하면 됩니다.

수식	빅오 표기	설명
		다항 함수로 구성되어 있으므로 최고 차항인 만 남아있습니다.
		다항 함수와 로그함수로 구성되어 있으므로 증가폭이 더 높은 만 남아있습니다.
		지수함수는 다항 함수보다 빠르게 증가하므로 지수 함수인 만 남습니다.
		최고 차항인 만 남습니다.

왜 이렇게 표현할까요?

아래와 같은 코드가 있습니다.

반복문 2번 만큼 수행

function solution(n){
    let count = 0;

    // 반복문을 n * 2번 수행
    for (let i = 0; i < n ; i += 1){
        for (let j = 0; j < n; j += 1) {
            count += 1;
        }
    }

    // 반복문 1번 n번 수행
    let count = 0;
    
    for (let i = 0; i < n; i += 1) {
        count += 1
    }
    
    // 반복문 2n번 수행
    let count = 0;
    
    for (let i = 0; i < 2 * n; i += 1) {
        count += 1
    }
    
    // 반복문 10번 연산수행
    let count = 0;
    
    for (let i = 0; i < 10; i += 1) {
        count += 1;
    }
}

console.log(solution(10));

위 solution 함수는 주석 영역별로 각각 , , 번의 증가 연산을 하며 결괏 값은 곧 연산 횟수임을 알 수 있습니다.

이때 solution 함수는 다음과 같이 표현할 수 있습니다.

해당 함수의 시간 복잡도는 가장 높은 차수인 를 가리켜 라고 말할 수 있습니다.

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 계수를 모두 지울까?

다음은 다양한 함수의 시간 복잡도를 가지고 있는 그래프입니다.

차항이 높을수록 폭의 크기가 커지는 것을 알 수 있습니다. 하지만 우리가 상한을 구하는 목적인 알고리즘의 성능을 가늠을 하기 위해서는 의미있는 상한을 구하는 것이 중요합니다.

예를들어 중학교 2학년의 학생을 표현할 다음 두 문장을 보겠습니다.

아직 고등학교에 입학하기 전이다. -> 참
아직 칠순 잔치를 하지 않았다. -> 참

두 문장은 모두 참이지만 (1)의 문장이 더욱 의미있는것을 알 수 있습니다. 우리는 이처럼 의미있는 최소한의 상한을 구하려고 하는 것이지 나머지 차수들은 구하지 않아도 되는 것을 알 수 있습니다.

시간 복잡도를 코딩 테스트에 활용하는 방법

우리는 이제 다음과 같은 정보를 알았습니다.

컴퓨터가 초당 연산할 수 있는 횟수는 1억 번으로 코딩 테스트의 문제 출제자는 보통 대부분의 코드를 정답 처리 할 수 있도록 채점 시간을 여유롭게 줍니다. 따라서 연산 횟수는 1,000 ~ 3,000만 정도로 고려해서 생각할 수 있습니다.

시간 복잡도별 최대 연산 횟수를 외울 필요는 없습니다. 연산 횟수의 간격이 매우 크기 때문에 '대략 데이터가 1,000만 개 정도면 O(N)을 사용해야 하는구나' 감을 익히는 것을 추천합니다.

시간 복잡도	최대 연산 횟수
	10
	20 ~ 25
	200 ~ 300
	3,000~ 5,000
	100만
	1,000 ~ 2,000만
	10억

앞서 배열에서 값을 찾는 로직은 하나하나 찾아가므로 시간 복잡도는 입니다. O(N)이 허용하는 연산 횟수는 1000만 이므로 데이터의 개수가 1000만 개 이하라면 이 알고리즘을 사용해도 됩니다.

Last modified: 07 August 2024