Big O

빅오 
알고리즘의 효율성을 평가함
Upper Bound for runtime 
 

• O(1): 입력 크기에 관계없이 일정한 실행 시간 또는 공간이 소요됩니다. 상수 시간 알고리즘을 나타냅니다.
• O(log n): 입력 크기의 로그에 비례하는 실행 시간이 소요됩니다. 로그 시간 알고리즘, 예를 들어 이진 탐색,를 나타냅니다.
• O(n): 입력 크기에 정비례하는 실행 시간이 소요됩니다. 선형 시간 알고리즘을 나타냅니다.
• O(n^2): 입력 크기의 제곱에 비례하는 실행 시간이 소요됩니다. 이차 시간 알고리즘, 예를 들어 이중 반복문을 사용하는 알고리즘,를 나타냅니다.

 
 

function addUpTo(n){
    return n * ( n + 1 ) / 2; 
}

연산횟수가 항상 3
O(1) - 상수
 

function addUpTo(n){
    let total = 0;
    for( let i = 1 ; i<=n ; i++ ){
        total += i;
    }
    return total;
}

연산횟수는 n이 커질 수록 늘어난다.
O(n) - 선형
 

function countUpAndDown(n){
    console.log('Going Up!');

    for( let i = 0; i<n; i++ ){
        console.log(i)
    }

    //O(n)

    console.log('At the top!\nGoing Down');

    for( let j = n-1 ; j>=0 ; j--){
        console.log(j);
    }

    //O(n)

    console.log('Back down. Bye!')
}

합쳐서 2 * O(n)이라고 할 수 있으나 그냥 O(n)이라고 함
 

function printAllPairs(n){
    for( let i = 0 ; i<n ; i++){
        for( let j = 0 ; j<n ; j++){
            console.log(i,j)
        }
    }
}

O(n)이 두개 중첩되어있음 - O(n^2)
그래프로 그려보면 선형이 아니다 지수 곡선이 나온