728x90

시간 복잡도(Time Complexity)는 알고리즘의 효율성을 나타내는 개념으로, 알고리즘이 실행되는 데 걸리는 시간을 입력 크기에 대한 함수로 표현한다. 시간 복잡도는 주로 빅오 표기법(Big-O Notation)을 사용하여 나타낸다.

시간 복잡도의 기본 개념

빅오 표기법(Big-O Notation)

빅오 표기법은 알고리즘의 성능을 나타내기 위해 가장 널리 사용되는 표기법이다. 입력 크기 ( n )이 무한히 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지를 나타낸다. 빅오 표기법은 상수 계수를 무시하고 가장 높은 차수의 항만을 고려한다.

시간 복잡도 종류

O(1) - 상수 시간 복잡도

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

def example_function():
    return 1

O(log n) - 로그 시간 복잡도

입력 크기가 증가할 때 실행 시간이 로그 형태로 증가하는 알고리즘이다. 예: 이진 탐색.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

O(n) - 선형 시간 복잡도

입력 크기에 비례하여 실행 시간이 증가하는 알고리즘이다. 예: 배열에서의 선형 탐색.

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

O(n log n) - 로그 선형 시간 복잡도

입력 크기와 로그의 곱에 비례하여 실행 시간이 증가하는 알고리즘이다. 예: 병합 정렬, 퀵 정렬.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

O(n^2) - 이차 시간 복잡도

입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘이다. 예: 버블 정렬, 삽입 정렬.

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

O(2^n) - 지수 시간 복잡도

입력 크기가 증가할 때 실행 시간이 지수 형태로 증가하는 알고리즘이다. 예: 피보나치 수열의 재귀적 구현.

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

O(n!) - 팩토리얼 시간 복잡도

입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘이다. 예: 외판원 문제의 완전 탐색.

import itertools

def traveling_salesman(points):
    min_path = float('inf')
    for perm in itertools.permutations(points):
        current_path = 0
        for i in range(len(points)):
            current_path += distance(perm[i], perm[(i+1) % len(points)])
        min_path = min(min_path, current_path)
    return min_path

마무리

시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 척도이다. 알고리즘을 설계할 때는 가능한 효율적인 알고리즘을 선택하고, 빅오 표기법을 사용하여 그 성능을 분석해야 한다. 추가적으로, 시간 복잡도와 함께 공간 복잡도도 고려하는 것이 중요하다.

컴퓨터온열마사지학과 수석졸업생

코드 예제로 보는 시간복잡도의 개념 (a.k.a. 빅오, Big-O)