[자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법

어떤 알고리즘이 효율적인지 판단하는 지표로는 크게 실행 소요 시간 측면에서 분석하는 시간 복잡도, 공간 측면에서 분석하는 공간 복잡도를 추정하여 판단한다.

 

 

 

시간 복잡도(Time Complexity)

시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로 알고리즘이 수행되는데 필요한 시간을 상대적인 지표로 나타낸 것이다. 즉, 어떠한 알고리즘이 얼마나 많은 시간이 걸리는지 나타내는데 쓰인다. 주로 빅오 표기법으로 나타낸다.

시간 복잡도는 알고리즘의 수행 시간을 분석한 결과다.

 

공간 복잡도(Space Complexity)

시간 복잡도가 말 그대로 시간과 관련되어 있듯이 공간 복잡도도 공간과 관련되어 있다. 즉, 어떠한 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타내는데 쓰인다. 

공간 복잡도는 알고리즘의 메모리 사용량을 분석한 결과다.

 

빅오 표기법(Big-O Notation)

점근적 표기법은 입력 데이터 n이 매우 커질 때 알고리즘의 복잡도가 증가하는 패턴을 근사적으로 표현한 것으로 크게 빅 오, 오메가, 세타 표기법이 있다.

O (빅 오)	상한선(upper bound)
Ω (오메가)	하한선 (lower bound)
Θ (세타)	상한-하한선 (upper and lower bound)

 

하지만 이 중에서 알고리즘의 효율성을 판단하는 데에는 빅 오 표기법이 가장 많이 쓰인다.

 

빅오 표기법은 상한 접근 즉, 최악의 경우를 나타내며 만약 입력 데이터 n이 들어오면 n번까지 수행해야 알고리즘이 종료된다.

 

빅오 표기법의 수학적 정의는 아래와 같다.

 

빅오 표기법의 복잡도 순서
O(1) > O(log n) > O(n) > O(n*log n) > O(n²) > O(2ⁿ) > O(n!)

 

 

O(1): 상수형

입력의 크기에 관계없이 항상 같은 시간을 소모한다.

배열에서 특정 인텍스의 값에 접근할 때 사용한다.

def get_element_at_index(arr, index):
    return arr[index]

arr = [10, 20, 30, 40, 50]
index = 2
print(get_element_at_index(arr, index)) # 30

 

O(log n): 로그형

입력의 크기가 커질수록 실행 시간은 느리지만 다른 형태에 비해 느린 증가율을 보인다.

주로 이진 탐색에 많이 쓰인다.

def binary_search(target, data):
    data.sort()
    start = 0 			
    end = len(data) - 1 	

    while start <= end:
        mid = (start + end) // 2 

        if data[mid] == target:
            return mid 		

        elif data[mid] > target: 
            end = mid - 1
        else:                   
            start = mid + 1
    
    return -1

# 예시
data = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(target, data)
print(result) # 3

 

O(n): 선형

입력 크기에 비례하여 실행 시간이 증가한다.

단순한 배열 순회나 선형 검색에서 자주 사용된다

def sum_of_elements(arr):
    total = 0
    for num in arr:
        total += num
    return total

# 예시
arr = [1, 2, 3, 4, 5]
result = sum_of_elements(arr)
print(result)  # 15

 

O(n*log n): 선형 로그형

주로 효율적인 정렬 알고리즘에서 나타난다.

특히 병합 정렬에서 나타난다.

def merge_sort(data):
    if len(data) <= 1:
        return data

    mid = len(data) // 2
    left_half = merge_sort(data[:mid])
    right_half = merge_sort(data[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_data = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_data.append(left[i])
            i += 1
        else:
            sorted_data.append(right[j])
            j += 1

    sorted_data.extend(left[i:])
    sorted_data.extend(right[j:])

    return sorted_data

# 예시
data = [38, 27, 43, 3, 9, 82, 10]
sorted_data = merge_sort(data)
print(sorted_data)  # [3, 9, 10, 27, 38, 43, 82]

 

O(n²):  이차형

입력 크기의 제곱에 비례하여 실행 시간이 증가한다.

보통 중첩된 알고리즘에서 나타나며 대표적으로 버블 정렬이 있다.

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

# 예시
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print(data)  # [11, 12, 22, 25, 34, 64, 90]

 

O(2ⁿ): 지수형

입력 크기가 증가함에 따라 실행 시간이 급격히 증가한다.

입력의 크기가 작을 때는 처리 가능하지만 조금만 커져도 급격히 증가하므로 효율적이지 않아 잘 사용되지 않는다.

 

O(n!): 팩토리얼형

매우 비효율적인 알고리즘이다.

지수형보다 더 비효율적으로 잘 사용되지 않는다.

 

 

아래는 자료구조별 시간 복잡도와 공간 복잡도를 나타낸 것이다.