알고리즘 특강 - 1. 시간복잡도, 공간복잡도

시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

꼭 최악의 경우를 기준으로 계산!

시간 복잡도는 Big-O(빅오) 표기법으로 표시. 빅오 표기법에서는 N의 지수부분만이 유효하게 쓰이고 나머지는 절삭함

 

[시간 복잡도 계산 예시]

function find_max_num(array) {

    let max_num = array[0]; // 연산 1번 실행

    for (let num of array) {

        // array 의 길이만큼 아래 연산이 실행

        if (num > max_num) {

            // 비교 연산 1번 실행

            max_num = num; // 대입 연산 1번 실행

        }

    }

    return max_num;

}

console.log('정답 = 6 / 현재 풀이 값 = ', find_max_num([3, 5, 6, 1, 2, 4]));

console.log('정답 = 6 / 현재 풀이 값 = ', find_max_num([6, 6, 6]));

console.log('정답 = 1888 / 현재 풀이 값 = ', find_max_num([6, 9, 2, 7, 1888]));

 

입력

• array의 원소 갯수 = N

실행 시간

• max_num 대입 연산 = 1번 
• max_num 대입 연산 1번 + array의 길이 X (비교 연산 1번 + 대입 연산 1번) = 1 + 2N 
• 마찬가지로 이 함수는 2N + 1의 시간이 걸렸겠구나! 라고 말할 수 있습니다. 
• 하지만, 빅오 표기법에서는 N의 지수부분만이 유효하게 쓰이고 나머지는 절삭하기 때문에
  2N + 1 → O(N)입니다.

 

공간 복잡도

문제를 해결하는데에 대한 공간과의 상관관계로, N개의 입력이 주어지면 공간을 얼마나 쓰는지 나타내는 것.

공간 복잡도는 시간 복잡도에 비해서는 중요한 지표는 아니므로 알고리즘의 성능 향상을 하기 위해선 공간을 필수적으로 더 사용해야 한다면 주저하지말기

function largest_product(my_list) {

    let products = [];

    for (let a of my_list) {

        for (let b of my_list) {

            // products 배열에 원소가 들어가는 이 연산은 (a * b)번이 실행되겠죠? 2중 루프!

            products.push(a * b);

        }

    }

    // 따라서, products의 공간 복잡도는 O(N^2)

    return Math.max(...products);

}

let myList = [1, 3, 5, 7, 9];

console.log(largest_product(myList));