[PCCP] 시간복잡도

알고리즘의 시간 복잡도와 빅오(Big-O) 분석

알고리즘을 설계하고 선택할 때 가장 중요한 요소 중 하나는 시간 복잡도입니다. 시간 복잡도는 입력 데이터의 크기가 증가함에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타내는 지표로, 효율성을 가늠하는 핵심 척도입니다. 이번 글에서는 대표적인 정렬, 탐색, 그래프 알고리즘과 자료구조의 시간 복잡도를 살펴보고, 입력 크기 10, 10,000, 1,000,000, 100,000,000일 때 각 빅오 표기법에 따른 계산 결과를 표로 정리해보겠습니다.

---

1. 시간 복잡도란?

시간 복잡도는 알고리즘이 문제를 해결하기 위해 필요한 연산 횟수를 입력 크기 ( n )의 함수로 표현한 것입니다.

• 목적: 알고리즘이 데이터가 많아졌을 때 얼마나 효율적으로 동작하는지 예측할 수 있도록 도와줍니다.
• 표현 방법: 가장 일반적으로 Big-O 표기법을 사용하며, 이는 최악의 경우를 나타냅니다.

대표적인 Big-O 표기법에는 다음과 같은 것들이 있습니다.

• O(1): 상수 시간 – 입력 크기와 관계없이 항상 일정한 시간이 소요됨
• O(log n): 로그 시간 – 입력 크기가 증가해도 연산 횟수는 느리게 증가함 (보통 log₂n 사용)
• O(n): 선형 시간 – 입력 크기에 비례하여 연산 횟수가 증가
• O(n log n): 선형 로그 시간 – 대부분의 효율적인 정렬 알고리즘에서 나타남
• O(n²): 이차 시간 – 중첩 반복문 등이 있을 때 나타나며, 입력 크기가 커질수록 연산 횟수가 급격히 증가

---

2. 대표적인 알고리즘과 자료구조의 시간 복잡도

정렬 알고리즘

알고리즘	평균 시간 복잡도	최악 시간 복잡도	특징 및 설명
버블 정렬	O(n²)	O(n²)	단순하지만 비교 횟수가 많아 비효율적임
삽입 정렬	O(n²)	O(n²)	대부분의 경우 간단한 구현과 적은 데이터 이동, 거의 정렬된 경우 O(n)
선택 정렬	O(n²)	O(n²)	매번 최소값을 찾아 교환하는 방식으로 항상 O(n²)
합병 정렬	O(n log n)	O(n log n)	분할 정복 방식, 안정적인 정렬, 추가 메모리 필요
퀵 정렬	O(n log n)	O(n²)	평균적으로 매우 빠르지만, 피벗 선택이 좋지 않을 경우 최악의 성능
힙 정렬	O(n log n)	O(n log n)	비교 기반 정렬, 추가 메모리 없이 정렬 가능

탐색 알고리즘

알고리즘	시간 복잡도	특징 및 설명
선형 탐색	O(n)	순차적으로 모든 요소를 검사
이진 탐색	O(log n)	정렬된 배열에서 중간값을 기준으로 범위를 절반씩 줄임

그래프 알고리즘

알고리즘	시간 복잡도	특징 및 설명
너비 우선 탐색 (BFS)	O(V + E)	모든 정점과 간선을 한 번씩 방문하며 최단 경로 탐색에 활용
깊이 우선 탐색 (DFS)	O(V + E)	재귀 또는 스택을 이용, 경로 탐색 및 연결 요소 분석에 사용
다익스트라 알고리즘	O(E log V)	음의 가중치가 없는 그래프에서 최단 경로 탐색 (우선순위 큐 사용 시)
벨만-포드 알고리즘	O(VE)	음수 가중치를 허용하며 모든 간선을 반복 검사
플로이드-워셜 알고리즘	O(V³)	모든 쌍의 최단 경로를 구하는 알고리즘
크루스칼 알고리즘	O(E log V)	최소 신장 트리(MST) 구성, 간선들을 정렬 후 합치는 방식
프림 알고리즘	O(E log V)	MST 구성, 우선순위 큐를 활용하여 인접 정점을 효율적으로 선택

자료구조 연산

자료구조	연산	평균 시간 복잡도	최악 시간 복잡도	특징 및 설명
배열/리스트	인덱스 접근	O(1)	O(1)	임의 접근이 빠름
배열/리스트	순차 탐색	O(n)	O(n)	모든 요소를 한 번씩 검사
해시 테이블	삽입/검색/삭제	O(1)	O(n) (최악의 경우 충돌 시)	평균적으로 매우 빠르지만, 충돌이 많으면 성능 저하 가능
이진 탐색 트리 (균형 트리)	삽입/검색/삭제	O(log n)	O(log n)	AVL, 레드-블랙 트리 등이 해당, 트리의 균형 유지가 중요
이진 탐색 트리 (비균형)	삽입/검색/삭제	O(log n)	O(n)	한쪽으로 치우칠 경우 성능이 선형적으로 저하됨

---

3. 입력 크기에 따른 빅오 계산 결과

입력 크기 ( n )이 10, 10,000, 1,000,000, 100,000,000일 때, 각 빅오 표기법에 따른 연산 횟수를 대략적으로 계산해보면 다음과 같습니다. (여기서 로그는 밑 2, 즉 ( \log_2 n )를 사용합니다.)

빅오 표기법	n = 10	n = 10,000	n = 1,000,000	n = 100,000,000
O(1)	1	1	1	1
O(log n)	약 3.32	약 13.29	약 20	약 26.58
O(n)	10	10,000	1,000,000	100,000,000
O(n log n)	약 33.2	약 133,000	약 20,000,000	약 2,660,000,000
O(n²)	100	100,000,000	1,000,000,000,000	10,000,000,000,000,000

주의: 위 값들은 이론적인 대략의 연산 횟수를 나타내며, 실제 알고리즘의 실행 시간은 상수 계수, 하드웨어 성능, 구현 방식 등 다양한 요인에 따라 달라질 수 있습니다.

이 표를 통해 입력 데이터의 크기가 커질수록 특히 O(n log n)나 O(n²)와 같은 알고리즘의 계산량이 어떻게 급격히 증가하는지 쉽게 확인할 수 있습니다.

---

4. 결론

알고리즘 선택 시 시간 복잡도를 고려하는 것은 매우 중요합니다.

• 작은 데이터셋: O(n²) 알고리즘도 문제가 없을 수 있으나,
• 큰 데이터셋: 보다 효율적인 O(n log n) 또는 O(n) 알고리즘을 선택해야 합니다.

이와 같이 시간 복잡도와 입력 크기에 따른 연산 횟수의 증가는 알고리즘의 성능을 예측하는 데 중요한 역할을 합니다. 효율적인 알고리즘 설계와 선택은 소프트웨어 성능 최적화의 핵심 요소임을 항상 염두에 두어야 합니다.

---

여러분도 다양한 알고리즘을 직접 구현해 보며 시간 복잡도가 실제 성능에 미치는 영향을 체감해 보시길 바랍니다. Happy Coding!