시간 복잡도(Time Complexity)는 알고리즘의 수행 시간을 나타내는 데 사용되는 개념입니다. 시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다. 일반적으로 더 작은 시간 복잡도를 가지는 알고리즘은 더 효율적으로 동작합니다.
시간 복잡도는 주로 Big O 표기법(Big O Notation)을 사용하여 표현됩니다. Big O 표기법은 알고리즘의 성능 상한을 나타내며, 가장 큰 영향을 주는 항만을 고려하여 나타냅니다. 몇 가지 흔히 사용되는 시간 복잡도의 예시를 살펴보겠습니다:
O(1) (상수 시간): 입력 크기에 관계없이 일정한 실행 시간을 가지는 알고리즘입니다. 예를 들어, 배열에서 인덱스를 이용해 요소를 찾는 작업은 O(1) 시간 복잡도를 가집니다.
O(log n) (로그 시간): 입력 크기에 대해 로그의 비례로 실행 시간이 증가하는 알고리즘입니다. 이진 탐색과 같은 분할 정복 알고리즘이 이에 해당합니다.
O(n) (선형 시간): 입력 크기에 정비례하여 실행 시간이 증가하는 알고리즘입니다. 배열 내에서 최댓값을 찾는 작업과 같은 순차적인 탐색이 O(n) 시간 복잡도를 가집니다.
O(n log n) (선형 로그 시간): 입력 크기에 대해 n과 로그 n의 곱으로 실행 시간이 증가하는 알고리즘입니다. 퀵 정렬과 병합 정렬 등이 이에 해당합니다.
O(n^2) (이차 시간): 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘입니다. 버블 정렬과 선택 정렬 등이 이에 해당합니다.
시간 복잡도는 알고리즘의 효율성을 평가하고 선택하는 데 중요한 지표입니다. 일반적으로 더 낮은 시간 복잡도를 가지는 알고리즘이 실행 시간 면에서 더 효율적입니다. 그러나 문제의 특성과 입력의 크기에 따라 알고리즘을 선택해야 하며, 최적의 알고리즘 선택은 시간 복잡도를 고려하여 이루어져야 합니다.