시간복잡도, Time Complexity, Big-O

Time Complexity(시간 복잡도)를 표기하는 방법

• Big-O → 상한점근
• Big-Ω → 하한점근
• Big-θ → 평균

시간 복잡도를 표기하는 3가지 방법이 있으며, 위부터 차례대로 최악의 경우, 최선의 경우, 평균의 경우에 대하여 나타내는 방법이다. 그중에서 Big-O 표기법은 최악의 경우를 고려하는 표기법 이므로 “이 정도 시간까지 걸릴 수 있다”를 명시적으로 보여주기에 그에 맞는 대응을 고려할 수 있게 해준다.

Big-O

Constant complexity - O(1)

• “일정한 복잡도”라고 하며, 입력 값 이 증가하더라도 시간이 늘어나지 않는다. 즉, 입력 값의 크기가 아무리 커져도 즉시 출력 값을 얻어낼 수 있다.

    function constantComplexity(arr, index){
        return arr[index];
    }
  
    let arr = [1,2,3,4,5];
    let index = 0;
    let result = constantComplexity(arr, index);
    console.log(result);

Linear complexity - for문 O(N)

• “선형 복잡도”라고 부르며, 입력 값이 증가함에 따라 시간 또한 같은 비율로 증가하게 된다. 즉, 입력 값의 크기와 같은 비율로 증가하는 복잡도를 가진다고 할 수 있다.

    function linearComplexity(num){
        for(let i = 0; i < 2*num; i++){
            console.log(i);
        }
    }
    let num = 10;
    linearComplexity(num);

Logarithmic complexity- O(logN)

• “로그 복잡도”라고 하며, Big-O 표기법 중 두 번째로 빠른 시간 복잡도를 가진다. Binary Search 와 같은 방법이며, up & down 게임 방식과 동일하다. 2진 검색은 정렬되지 않은 배열에서 사용할 수 없다.

    function logarithmicComplexityV1(num){
        let i = num;
            while(i > 0){
                console.log(i);
                i /= 2;
            }
    }
  
    let num = 10;
    logarithmicComplexityV1(num);
  
    function logarithmicComplexityV2(num){
        let i = 1;
            while(i < num){
                console.log(i);
                i *= 2;
            }
    }
  
    logarithmicComplexityV2(num);

Quadratic complexity - n중 for문 O(N^n)

• “2차 복잡도”라고 부르며, 입력 값이 증가 함에 따라 시간이 N의 n제곱 수의 비율로 증가하는 것을 말한다.

    function quadraticComplexity(num){
        for(let i = 0; i < num; i++){
            console.log(i);
            for(let j = 0; j < num; j++){
                console.log(j);
            }
        }
    }
  
    let num = 10;
    quadraticComplexity(num);

Exponential complexity - $O(C^N)$

• “기하급수적 복잡도”라고 하며, Big-O 표기법 중 가장 느린 시간 복잡도를 갖는다. 입력 값이 증가함에 따라 지수가 증가하기 때문에 극한 함수와 같은 특성을 지닌다. 구현한 알고리즘이 해당 복잡도를 갖고 있다면 다른 접근 방식을 찾는 것이 좋다.

    function exponentialComplexity(num){
        if(num <= 1){
            return 1;
        }
        return exponentialComplexity(num - 1) + exponentialComplexity(num - 2);
    }
  
    let num = 10;
    exponentialComplexity(num);
    // don't do it num = 100; your computer is end