본문으로 건너뛰기

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

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

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

  • 'O' (Big O): '차수(Order)'를 뜻하며, 알고리즘의 시간 복잡도나 공간 복잡도를 표현합니다. 'O'는 'Order of' 즉, '...의 차수'라는 의미로, 알고리즘이 입력 크기에 대해 얼마나 많은 계산이나 메모리가 필요한지를 나타내는 상한선을 표현합니다.

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

예를 들어 'O(1)'은 알고리즘의 실행 시간이 입력 크기와 관계없이 일정한 것을 뜻하고, 'O(n)'은 알고리즘의 실행 시간이 입력 크기에 선형적으로 비례하는 것을 나타내며, 'O(n²)'은 입력 크기의 제곱에 비례하여 실행 시간이 기하급수적으로 증가함을 의미합니다.


알고리즘의 복잡도 평가

알고리즘의 복잡도는 시간 복잡도공간 복잡도 두 가지 측면으로 평가힙니다.

  1. 시간 복잡도 (Time Complexity): 알고리즘이 문제를 해결하는 데 걸리는 시간이 얼마나 되는지를 나타냅니다. 일반적으로 입력 크기에 따라 얼마나 많은 단계가 필요한지로 측정됩니다. 예를 들어 간단한 반복문은 입력 크기에 비례하는 '선형 시간 복잡도(O(n))'를 가지며, 중첩된 반복문은 '제곱 시간 복잡도(O(n²))'를 갖습니다.

  2. 공간 복잡도 (Space Complexity): 알고리즘이 실행될 때 필요한 메모리 공간의 양을 뜻합니다. 예를 들어, 고정된 수의 변수만을 사용하는 알고리즘은 '상수 공간 복잡도(O(1))'를 가지며, 입력 크기에 비례하는 추가 메모리가 필요한 경우 '선형 공간 복잡도(O(n))'를 가집니다.