알고리즘 복잡도 개념 복습

알고리즘 복잡도는 알고리즘이 얼마나 효율적인지를 나타내는 척도로, 이번 수업에서는 이전에 배운 빅오 표기법과, 시간 복잡도와 공간 복잡도의 개념을 복습하겠습니다.

빅 오 표기법(Big O notation)은 알고리즘의 시간 복잡도나 공간 복잡도를 나타내는 데 사용되는 수학적 표현 방식입니다.

이 표기법은 알고리즘이 어떤 문제를 해결하는 데 필요한 자원(시간 또는 공간)이 입력 크기에 따라 어떻게 변하는지를 나타냅니다.

• O(1) 상수 시간 : 입력 크기와 상관없이 일정한 시간이 걸립니다.

• O(n) 선형 시간 : 알고리즘의 실행 시간이 입력 크기에 선형적으로 증가합니다.

• O(n^2) 제곱 시간 : 입력 크기가 두 배가 되면, 실행 시간은 네 배가 됩니다. 이중 반복문 이에 해당합니다.

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 소요되는 시간이 입력 크기에 따라 어떻게 변하는지를 나타냅니다. 주로 알고리즘이 최악의 경우에 얼마나 많은 연산이 필요한지를 대략적으로 나타냅니다.

예를 들어, 아래 코드는 입력의 크기가 5일 때는 5번의 연산이 필요하고, 입력의 크기가 10일 때는 10번의 연산이 필요합니다.

복사
def example_function(n):
    for i in range(n):
        print(i)

# 함수 호출
example_function(5)

따라서 위와 단순 반복문의 시간 복잡도는 입력의 크기(n)에 따라 비례해서 증가하는 O(n)이 됩니다.

공간 복잡도는 알고리즘 실행 중 사용되는 총 메모리 공간의 양을 나타내는 척도입니다.

예를 들어, 아래 함수는 입력의 크기(n)에 관계없이 항상 고정된 크기의 배열을 사용하므로, 공간 복잡도는 O(1)이 됩니다.

복사
def example_function():
    fixed_array = [1, 2, 3, 4, 5] # 고정된 크기의 배열 차지
    print(fixed_array)

# 함수 호출
example_function()