알고리즘의 복잡도(Complexity)란?

알고리즘의 복잡도는 알고리즘이 얼마나 효율적인지를 평가하는 방법으로, 보통 빅 오 표기법(Big O notation)으로 표현합니다.

빅 오 표기법은 입력 크기에 따라 알고리즘의 실행 시간이나 메모리 사용량이 어떻게 증가하는지를 나타내며, 아래와 같은 형태로 표현됩니다.

여기서 O와 n의 의미는 다음과 같습니다.

• 'O' (Big O): 알고리즘의 차수(Order)를 나타내며, 시간 복잡도와 공간 복잡도를 측정합니다. O는 Order of의 약자로, 알고리즘이 입력 크기에 따라 요구하는 계산량이나 메모리 사용량의 상한선을 의미합니다.

• 'n': 일반적으로 알고리즘의 입력 크기를 나타내는 변수입니다.

예를 들어 각 복잡도의 의미는 다음과 같습니다.

• O(1)은 알고리즘의 실행 시간이 입력 크기와 관계없이 일정한 시간이 소요

• O(n)은 알고리즘의 실행 시간이 입력 크기에 선형적으로 비례하여 증가

• O(n²)은 실행 시간이 입력 크기의 제곱에 비례하여 기하급수적으로 증가

알고리즘의 복잡도는 시간 복잡도와 공간 복잡도 두 가지 측면에서 평가됩니다.

시간 복잡도는 알고리즘이 문제를 해결하는 데 소요되는 시간을 나타냅니다.

주로 입력 크기에 따라 필요한 연산 단계의 수로 측정됩니다.

예를 들어, 단순 반복문은 입력 크기에 비례하여 수행되므로 선형 시간 복잡도, 즉 O(n)의 시간 복잡도를 갖습니다.

반면 for문 속에 또 다른 for문이 중첩되어 있는 경우, 입력 크기의 제곱만큼 연산이 필요하므로 제곱 시간 복잡도, 즉 O(n²)의 시간 복잡도를 갖습니다.

공간 복잡도는 알고리즘 실행 시 필요한 메모리 공간의 양을 나타냅니다.

메모리 공간의 양은 알고리즘이 사용하는 변수, 데이터 구조, 재귀 호출 스택 등의 크기를 포함합니다.

예를 들어, 고정된 수의 변수만 사용하는 경우는 상수 공간 복잡도, 즉 O(1)의 공간 복잡도를 갖습니다.

반면 입력 크기에 비례하는 메모리가 필요한 경우는 선형 공간 복잡도, 즉 O(n)의 공간 복잡도를 갖습니다.