알고리즘 시간복잡도와 Big-O

시작하기

어떤 알고리즘의 시간 복잡도(Time Complexity) / Big-O 를 논할 때
아래 그래프 정도만 숙지하고 있어도, 본인이 만든 코드의 시간 복잡도를 기반으로
대략적으로 계산 노드가 기하급수적으로 증가할 때 어떤 일이 벌어질 지 예측 가능합니다.

Big-O

Big-O 표기법의 특징

상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어 O(3N) => O(N)와 같이 상수항은 무시하고 표기합니다.

영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

예를들어 O(N²+3N+2) => O(N²)와 같이 영향력이 지배적인 이외에 영향력이 없는 항들은 무시한다.

• O(1) : 스택에서 Push, Pop
• O(log n) : 이진트리
• O(n) : for 문
• O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
• O(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
• O() : 피보나치 수열

big-O에는 다양한 실행 시간이 존재하지만 자주 사용 되는 것들은 다음과 같습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

N의 값	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229401496703205376
O(N!)	1	3628800	화면에 표현할 수 없음!

Big-O: function ranking

O(1)

function sum(num1, num2) {
    return num1 + num2;
};

이 기능은 O(1)입력과 관련하여 시간 (또는 “일정 시간”)으로 실행됩니다. 입력 배열은 1 개 항목 또는 1,000 개 항목 일 수 있지만이 기능은 여전히 ​​한 단계 만 필요합니다.

O(log n)

function log(n){
    for(var i = 1; i <= n; i = i * 3){
        console.log('i', i)
    }
}

배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.

O(n)

function forLoop(){
    for(var i = 0; i < 10; i++){
        console.log('i',i);
    }
}

이 함수는 O(n)시간 (또는 “선형 시간”)으로 실행되며 여기서 n배열의 항목 수입니다. 배열에 10 개의 항목이 있으면 10 번 출력해야합니다. 항목이 1000 개이면 1000 번 출력해야합니다.

O(n²)

function forLoop(){
    for(var i = 0; i < 10; i++){
        for(var j = 0; j < 10; j++){
            console.log('i, j',i, j);
        }
    }
}

여기에 두 개의 루프가 중첩됩니다. 배열에 n항목 이있는 경우 외부 루프가 반복 될 때마다 외부 루프 실행 n시간과 내부 루프 실행 n시간이 발생하여 총 2 회 출력됩니다. 따라서 이 함수는 O(n²)시간 (또는 “이차 시간”)으로 실행됩니다. 배열에 10 개의 항목이 있으면 100 번 출력해야합니다. 1000 개 항목이있는 경우 1000000 회 출력해야합니다.

O(2ⁿ)

function fibonacci(num){
    if (num <= 1) return num;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

O(2ⁿ)함수의 예는 피보나치 수의 재귀 계산입니다. O(2ⁿ)은 입력 데이터 세트에 추가 될 때마다 성장이 두 배가되는 알고리즘을 나타냅니다. O(2ⁿ)함수의 성장 곡선은 기하 급수적으로 매우 얕게 시작하여 기상 적으로 상승합니다.

Fibonacci