시간복잡도란?

코딩 테스트에서 효율적인 알고리즘을 작성하려면 시간복잡도를 이해하는 것이 필수다.

상위 문제일수록 주어진 문제를 해결하는 데 얼마나 빠르게 동작하는지를 고려해야 한다. 

시간복잡도란?

시간복잡도(Time Complexity)란 입력값이 증가할 때 알고리즘의 실행 시간이 어떻게 변하는지를 나타내는 척도이다.

입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산해서 알고리즘의 수행 시간을 평가하는 방법이다.

대부분은 시간복잡도를 수학적으로 표현할 때 빅오 표기법(Big-O Notation)을 사용한다.

빅오는 최악의 경우를 기준으로 알고리즘의 성능을 분석하는 방식이다.

 

가장 많이 쓰는 것은 빅오 표기법이지만, 그 외에도 다양한 표기법이 있다.

1. 빅오(Big-O) 표기법

최악의 경우(Worst Case)를 기준으로 알고리즘의 시간복잡도를 나타낸다. 코딩 테스트나 면접에서는 주로 빅오 표기법을 사용한다.

• 입력 크기(N)가 증가할 때, 실행 시간이 최악의 경우, 즉 코드가 가장 느리게 실행되는 경우, 어떻게 증가하는지를 나타낸다.
• 최대 시간 복잡도를 고려하기 때문에, 알고리즘의 성능을 보수적으로 평가할 수 있다.

2. 빅오메가(Big-Ω) 표기법

최상의 경우(Best Case)를 기준으로 알고리즘의 실행 시간을 나타낸다.

• 빅오 표기법과 반대로 코드가 가장 빠르게 실행될 때의 시간복잡도를 분석한다.
• 하지만 실제 실행 속도를 보장하지 않기 때문에, 성능 평가에는 많이 사용되지 않는다.

3. 빅세타(Big-Θ) 표기법

평균적인 경우(Average Case)를 기준으로 알고리즘의 실행 시간을 나타낸다.

• 알고리즘의 상한과 하한이 일치하는 경우 사용한다. 즉, 최악의 경우와 최상의 경우가 비슷한 알고리즘에서 가장 많이 쓰인다.
• 정확한 실행 시간 경계를 나타낼 수 있다.

 

예제를 통해 시간복잡도 표기법 비교

def find_element(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

function findElement(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

• 최악의 경우(배열 끝에서 찾는 경우) => 빅오 표기법 : O(N)
• 최상의 경우 (첫 번째 요소가 목표값인 경우) => 빅오메가 표기법 : Ω(1)

주요 시간복잡도 비교

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

주요 시간복잡도와 예제

O(1) - 상수 시간

입력 크기와 상관없이 일정한 시간이 걸리는 알고리즘이다.

배열의 크기와 무관하게 항상 한 번만 실행되므로 O(1)이다.

def get_first_element(arr):
    return arr[0]  # 첫 번째 원소 반환 (O(1))

function getFirstElement(arr) {
    return arr[0]; // 첫 번째 원소 반환 (O(1))
}

O(log N) - 로그 시간

입력 크기가 증가할 때 실행 시간이 로그 형태로 증가하는 경우이다. 대표적으로 이진 탐색(Binary Search)이 있다.

배열이 정렬되어 있을 때 절반씩 탐색을 줄여가므로 O(log N)이다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 찾지 못한 경우

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

O(N) - 선형 시간

입력 크기에 비례하여 실행 시간이 증가하는 경우이다. 보통 단순 반복문에서 나타난다.

배열을 처음부터 끝까지 확인해야 하므로 O(N)이다.

def find_element(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

function findElement(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

O(N log N) - 선형 로그 시간

대표적으로 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort) 등의 정렬 알고리즘이 O(N log N)의 시간복잡도를 가진다.

정렬 알고리즘에서 분할 과정이 O(log N), 합치는 과정이 O(N)이므로 O(N log N)이다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

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

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

O(N²) - 이차 시간

중첩 반복문이 사용될 때 나타난다. 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort) 등이 해당한다.

이중 반복문이 있으므로 O(N²)이다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

O(2^N) - 지수 시간

입력 크기가 증가할 때 실행 시간이 지수적으로 증가하는 경우이다. 피보나치 재귀(Fibonacci Recursion)가 대표적이다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

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