시간복잡도

시간복잡도에 대해서 알아봅니다.
시간복잡도는 어떠한 알고리즘을 실행하는데 있어서 공간과 시간을 얼마나 차지하는지에 대해 나타내는 지표입니다. 즉, 우리는 시간복잡도를 보고 알고리즘의 성능과 효율성을 판단할수 있습니다.

BIG O

BIG O는 알고리즘의 성능을 수학적으로 표기해주는 기법입니다.
O()로 표시하고 괄호 안에 성능에 대한 수치를 표기해줍니다. BIG O는 해당 알고리즘의 정확한 성능을 표기하기보다, 어느정도의 복잡성을 갖고 계산하는지에 대한 단계를 구분하게 해줍니다.

위 그림은 시간복잡도를 직관적으로 알수 있는 그래프 입니다.

다음으로 BIG O의 대표적인 표기법에 대해 알아보겠습니다.

O(1) - constant time

O(1) 알고리즘은 입력하는 데이터의 크기나 양에 상관없이 항상 1 만큼의 시간이 걸리는 알고리즘 입니다. 이 알고리즘은 항상 1 만큼의 시간을 사용하기 때문에 가장 빠른 종류의 알고리즘이라고 할수 있습니다.

const test = function(){
	console.log("Hey!");
}

위의 코드의 경우 시간복잡도는 O(1)이라고 할수 있습니다.

O(log n) - log time

O(log n) 알고리즘은 탐색을 하는 알고리즘이라고 가정한다면, 어떠한 기준에 의해 분류되어 탐색하는 알고리즘의 복잡도 입니다.
대표적인 예로는 Binary Search Tree가 있는데요. 조금 더 쉬운 예를 들자면 숫자 1~100까지 Up, Down으로 랜덤한 숫자를 맞추는 게임의 알고리즘이 O(log n)의 시간복잡도를 가진다고 할수 있습니다.

O(n) - linear time

O(n) 알고리즘은 처리해야 할 데이터의 갯수만큼 시간이 늘어나는 알고리즘의 복잡도 입니다.
코드를 통해 바로 알아보도록 하겠습니다.

for(let i = 0; i < array.length; i++){
    doSomething(array[i]);
}

위의 코드를 보면 array가 갖고있는 인자의 갯수만큼 console.log를 반복하는 함수 입니다. 위의 경우 array의 크기가 커질수록 시간이 오래걸리는 함수이기 때문에 시간복잡도는 O(n)이 됩니다.

O(n^2) - quadratic time

O(n^2) 알고리즘은 데이터 수의 제곱에 비례하여 시간복잡도가 증가합니다. 이런 알고리즘은 어떠한 경우에도 시간이 오래걸리는 알고리즘이기 때문에 효율성과 성능 면에서 안좋은 알고리즘이라고 할수 있겠습니다. 대표적으로는 이중 for문이 O(n^2)의 시간복잡도를 갖습니다.

for(let i = 0; i < array.length; i++){
    for(let j = 0; j < array.length; j++){
        doSomething(i,j);
    }
}

이번 글에서는 시간복잡도에 대해 알아보았습니다.