[알고리즘] 빅O 표기법 & 왜 공간 복잡도가 시간 복잡도 보다 중요도가 낮을까?

알고리즘의 시간 복잡도는 알고리즘의 효율성을 이해하고 비교하는 데 중요한 지표 중 하나입니다. 이것은 알고리즘이 입력 크기에 따라 얼마나 빨리 실행되는지를 나타내는데, 일반적으로 "O 표기법"을 사용하여 표현됩니다. 여러 가지 표기법이 있지만, 주로 사용되는 표기법에 대해 알아보겠습니다.

 

1. O 표기법: 최악의 경우에도 알고리즘이 얼마나 빨리 실행될 수 있는지에 대한 상한을 나타냅니다. 이것은 주어진 알고리즘이 얼마나 빠르게 실행될 수 있는지에 대한 상한을 제공합니다.
2. Θ 표기법: 평균 복잡도를 나타냅니다. 이것은 알고리즘이 실행될 때 기대되는 작업량의 증가율을 나타냅니다.
3. Ω 표기법: 최선의 경우에도 알고리즘이 얼마나 빨리 실행될 수 있는지에 대한 하한을 나타냅니다. 이것은 주어진 알고리즘이 최상의 경우에 얼마나 빠르게 실행될 수 있는지를 제공합니다.

그런 다음, 여러 시간 복잡도의 예시를 살펴봅시다.

 

• O(1): 상수 시간복잡도로, 입력 크기와 상관없이 일정한 시간이 걸리는 알고리즘입니다. 이는 배열의 첫 번째 요소를 출력하는 것과 같은 작업에서 볼 수 있습니다.

function printFirstElement(array) {
    console.log(array[0]);
}

 

• O(log n): 로그 시간복잡도로, 데이터 양이 증가해도 실행 시간이 로그 함수적으로 증가합니다. 예를 들어, 이진 검색 알고리즘이 이에 해당합니다.

function binarySearch(array, target) {
    let low = 0;
    let high = array.length - 1;
    
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1; // Target not found
}

• O(n): 선형 시간복잡도로, 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘입니다. 배열 순회나 선형 검색 알고리즘이 여기에 속합니다.

function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;
        }
    }
    
    return -1; // Target not found
}

• O(n²): 이차 시간복잡도로, 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘입니다. 이중 반복문을 사용한 작업이 여기에 해당합니다.

function findPairs(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            console.log(array[i], array[j]);
        }
    }
}

• O(n log n): 정렬 알고리즘이 이에 해당하며, 입력 크기와 로그 함수의 곱에 비례하여 실행 시간이 증가합니다.

function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }
    
    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));
    
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

시간 복잡도는 일반적으로 입력 크기가 커질수록 더 중요해집니다. 대용량 데이터베이스나 파일 처리와 같은 작업에서는 시간 복잡도가 작은 알고리즘이 선호됩니다. 그러나 입력 크기가 작을 때는 시간 복잡도가 크게 중요하지 않을 수 있습니다. 이 경우에는 알고리즘의 구현 난이도, 가독성, 유지보수성 등을 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다.

예를 들어, 배열 요소를 출력하는 함수를 보겠습니다.

이 함수는 입력 크기에 대해 로그 시간복잡도를 갖습니다. 처음에는 이중 반복문이 보입니다. 그러나 안쪽의 반복문은 j가 0부터 시작하여 점진적으로 증가하지 않고 2의 배수로 증가하므로 실제로는 로그 시간복잡도를 가집니다. 이 함수는 입력 크기에 따라 로그 함수적으로 증가하는 실행 시간을 가집니다.

알고리즘의 선택은 문제의 크기와 요구 사항에 따라 다르며, 시간 복잡도뿐만 아니라 구현의 복잡성과 가독성도 고려해야 합니다.

 

알고리즘 표기법에서 공간 복잡도도 있는데 굳이 설명하지 않는 이유는??

공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원공간의 양을 말합니다. 알고리즘이 얼마나 많은 메모리 공간을 차지하는지에 초점을 맞춰 효율성을 분석하는 지표라고 보면됩니다.

 

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간이 필요한지를 나타냅니다.
공간 복잡도는 크게 두가지로 나뉠 수 있는데요.

 

1. 알고리즘과 무관한 공간, 즉 고정공간으로 코드가 저장되는 공간을 뜻합니다.
코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요한 공간등이 그 예입니다.
2. 알고리즘과 밀접한 공간 즉 가변공간은 문제를 해결하기 위한 알고리즘이 필요로 하는 공간입니다.
변수를 저장하는 공간이 그예입니다.

요즘은 하드웨어의 발달로 인해 메모리 공간이 굉장히 넉넉해 졌기 때문에 공간 복잡도의 중요도가 많이 낮아졌다고 합니다.
따라서 알고리즘의 효율 성을 따질때는 시간 복잡도를 기준으로 많이 따집니다.