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

이번 수업에서는 알고리즘의 복잡도를 쉽게 이해할 수 있도록 간단한 파이썬 코드 예시와 함께 설명합니다.

시간 복잡도와 공간 복잡도를 통해 알고리즘이 얼마나 효율적인지 평가하는 방법을 배워보겠습니다.

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

선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 비례해 실행 시간이 증가합니다.

아래 코드는 리스트의 각 요소를 출력하는 간단한 예제입니다.

복사
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    print(number)

리스트의 크기가 커질수록 for 루프가 순회하는 횟수가 동일하게 증가합니다.

따라서 이 코드는 입력 크기 n에 비례하는 시간 복잡도, 즉 O(n)을 가집니다.

이차 시간 복잡도를 가지는 알고리즘은 입력 크기의 제곱에 비례해 실행 시간이 증가합니다.

아래는 중첩된 루프를 사용해 숫자 쌍의 조합을 출력하는 예제입니다.

복사
numbers = [1, 2, 3, 4, 5]

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

위 코드에서 첫 번째 for 반복문은 n번 실행되고, 각 반복마다 두 번째 for 반복문dl n번 실행됩니다.

따라서 총 n * n = n²번 실행되므로, 이 코드는 입력 크기 n의 제곱에 비례하는 시간 복잡도, 즉 O(n²)을 갖습니다.

공간 복잡도(Space Complexity)는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 나타냅니다.

상수 공간 복잡도를 가지는 알고리즘은 입력 크기와 관계없이 일정한 메모리만 사용합니다.

예를 들어, 아래 코드는 단순히 숫자의 제곱을 계산합니다.

복사
def square(number):
    return number * number

result = square(5)

print(result)

이 함수는 number 입력값과 결과값을 저장하기 위한 최소한의 메모리만 사용합니다.

입력 크기와 무관하게 일정한 메모리 요구량을 가지므로 공간 복잡도는 O(1)입니다.

선형 공간 복잡도를 가지는 알고리즘은 입력 크기에 비례해 메모리 사용량이 증가합니다.

아래는 리스트를 복제하는 예제입니다.

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

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

print(cloned)

clone_list 함수는 original_list의 길이에 비례하는 메모리를 사용하여 새로운 리스트를 생성합니다.

입력 리스트의 크기가 n이라면, 복제된 리스트도 동일한 크기 n만큼 메모리 공간을 차지합니다.

따라서 이 함수의 공간 복잡도는 O(n)입니다.