시간복잡도 공간복잡도 Big-O

Big-O 표기법이란?

알고리즘의 효율성을 평가할 때 가장 중요한 개념 중 하나가 바로 'Big-O 표기법'입니다. 알고리즘이 문제를 해결하는 데 얼마나 빠른지, 즉 실행 시간이 어떻게 증가하는지를 분류하는 방법입니다. 또한, 알고리즘이 실행될 때 필요한 메모리 양이 어떻게 증가하는지를 나타내는 데에도 사용됩니다.

시간복잡도(Time Complexity)

시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 단계의 수 또는 연산의 수를 나타냅니다. 예를 들어, 리스트의 모든 요소를 한 번씩만 확인하는 선형 검색 알고리즘은 시간복잡도가 O(n)으로 표현됩니다.

ex) 예제 1 - 선형 검색

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

# 리스트와 타겟 값을 사용하여 함수 호출
arr = [3, 5, 2, 4, 9]
x = 4
print(linear_search(arr, x))  # 출력: 3

공간 복잡도는 알고리즘의 메모리 사용량을 나타냅니다. 상수 공간을 사용하는 알고리즘은 O(1)의 공간 복잡도를 가지며, 입력 크기에 비례하여 메모리를 사용하는 알고리즘은 O(n)의 공간 복잡도를 가집니다.

ex)  예제 2- 합계 계산

def sum_array(arr):
    total = 0  # 총 합을 저장하기 위한 변수
    for i in arr:
        total += i
    return total

# 리스트를 사용하여 함수 호출
arr = [3, 5, 2, 4, 9]
print(sum_array(arr))  # 출력: 23

이 함수는 전체 합계를 계산하기 위해 하나의 변수만 사용하므로, 입력 크기와 상관없이 동일한 메모리를 사용합니다. 따라서 공간 복잡도는 O(1)입니다.

한 종류의 문제를 해결할 수 있는 방법은 여러 가지가 있을 수 있습니다. Big-O 표기법을 통해 우리는 각 알고리즘의 상대적인 성능을 비교하고 가장 효율적인 방법을 선택할 수 있습니다. 이제 시간복잡도와 공간복잡도를 더 깊이 이해하기 위해 복잡한 예제를 살펴보겠습니다.

시간복잡도의 또 다른 예: 이진 검색

이진 검색은 정렬된 리스트에서 특정 값의 위치를 찾을 때 사용할 수 있는 효율적인 알고리즘입니다. 시간복잡도는 O(log n)으로, 리스트의 크기가 커져도 연산 횟수가 로그 함수로 증가하기 때문에 매우 빠릅니다.

ex) 예제 3 - 이진 검색

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        # 찾은 경우 중간값 인덱스 반환
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1  # 찾지 못한 경우

# 정렬된 리스트와 타겟 값을 사용하여 함수 호출
arr = [2, 3, 4, 10, 40]
x = 10
print(binary_search(arr, x))  # 출력: 3

이진 검색 알고리즘은 중간 지점을 기준으로 탐색 범위를 반으로 줄여가면서 타겟 값을 찾습니다. 탐색 범위가 반씩 줄어들기 때문에 연산의 횟수는 log2(n)으로 표현할 수 있습니다.

공간 복잡도: 재귀 함수

재귀 함수는 자기 자신을 호출하여 문제를 해결하는 함수입니다. 재귀 함수의 공간 복잡도는 함수의 호출 횟수에 따라 달라집니다. 예를 들어, 간단한 팩토리얼 함수는 O(n)의 공간 복잡도를 가집니다.

파이썬 예제: 팩토리얼 계산

def factorial(n):
    # n이 1 이하인 경우 1을 반환
    if n <= 1:
        return 1
    else:
        # n! = n * (n-1)!
        return n * factorial(n-1)

# 숫자를 사용하여 함수 호출
print(factorial(5))  #

이 반복문 버전의 팩토리얼 함수는 결과값을 계산하기 위해 단일 변수만 업데이트하기 때문에 추가적인 메모리를 거의 사용하지 않습니다.