알고리즘의 시간, 공간 복잡도

알고리즘의 복잡도를 이해하기 위한 간단한 파이썬 코드 예시를 확인해 보겠습니다.

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 소요되는 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 척도입니다.

선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 직접 비례하여 시간이 증가합니다. 아래 코드는 주어진 리스트의 각 요소를 출력하는 간단한 예입니다.

Copy
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    print(number)

이 코드에서 for 루프는 리스트 numbers의 각 요소를 한 번씩 방문하므로, 리스트의 크기(n)에 비례하는 시간이 소요됩니다.

이차 시간 복잡도를 가지는 알고리즘은 입력 크기의 제곱에 비례하여 시간이 증가합니다. 아래 코드는 중첩된 루프를 사용하여 각 숫자 쌍의 조합을 출력합니다.

Copy
numbers = [1, 2, 3, 4, 5]

for i in numbers:
    for j in numbers:
        print(f"({i}, {j})")

이 코드에서 두 개의 중첩된 for 루프는 리스트 numbers의 모든 가능한 숫자 쌍을 생성합니다. 첫 번째 루프가 한 번 실행될 때마다 두 번째 루프가 전체 리스트를 순회하므로, 전체 작업 횟수는 n x n, 즉 n의 제곱에 비례합니다.

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 나타내며, 알고리즘이 사용하는 변수, 데이터 구조 및 할당된 메모리 양에 의해 결정됩니다.

상수 공간 복잡도는 입력 크기에 상관없이 알고리즘이 사용하는 메모리 양이 일정한 경우입니다. 예를 들어, 특정 수의 제곱을 계산하는 함수는 입력 크기와 상관없이 일정한 양의 메모리만을 사용합니다.

Copy
def square(number):
    return number * number

result = square(5)

print(result)

이 함수는 number라는 단 하나의 입력과, 그 입력의 제곱을 계산하는 임시 변수만을 사용합니다. 따라서, 이 함수의 공간 복잡도는 O(1)입니다.

선형 공간 복잡도는 알고리즘이 사용하는 메모리 양이 입력 크기에 비례해 증가합니다. 예를 들어, 입력 리스트의 모든 요소를 복사하여 새로운 리스트를 만드는 경우가 이에 해당합니다.

Copy
def clone_list(original_list):
    new_list = original_list[:]  # 리스트 전체를 복사
    return new_list

original = [1, 2, 3, 4, 5]
cloned = clone_list(original)

print(cloned)

이 함수에서 new_list는 입력 original_list의 크기만큼의 공간을 차지합니다. 입력 리스트의 크기가 n이라면, 복제된 리스트도 n만큼의 공간을 필요로 하므로, 이 함수의 공간 복잡도는 O(n)입니다.