시간 복잡도(Time Complexity)란?
시간 복잡도는 알고리즘이 특정 크기의 입력을 처리하는 데 걸리는 시간을 수학적으로 표현한 것입니다. 즉, 입력 데이터의 크기(n)가 증가할 때 실행 시간이 얼마나 빠르게 증가하는지를 나타내는 척도입니다.
시간 복잡도는 주로 빅오 표기법(Big-O Notation) 을 사용하여 표현하며, 알고리즘의 효율성을 분석하는 데 중요한 기준이 됩니다.
시간 복잡도 계산의 예시
알고리즘의 시간 복잡도를 빠르게 파악하는 데 도움이 되는 몇 가지 일반적인 예시는 다음과 같습니다.
-
O(n): 단일 루프를 사용하여 입력 데이터 전체를 한 번 순회하는 경우
- 예: 1차원 배열의 모든 요소 탐색
-
O(n²): 중첩된 루프를 사용하여 입력 데이터를 두 번 순회하는 경우
- 예: 2차원 배열의 모든 요소 탐색, 버블 정렬
-
O(n * m): 크기가 다른 두 개의 입력 데이터를 각각의 루프에서 순회하는 경우
-
O(n log n): 입력 데이터를 정렬하거나, 분할 정복(Divide and Conquer) 방식을 사용하는 경우
- 예: 퀵 정렬, 병합 정렬
-
O(log n): 입력 데이터의 크기가 절반씩 줄어드는 탐색을 수행하는 경우
- 예: 이진 탐색
-
O(1): 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 경우
- 예: 배열의 특정 인덱스에 접근