[C++ 코딩테스트] 시간복잡도

⏰ 시간 복잡도의 개념 및 표기법

 

1. 시간 복잡도란?

• 정의: 입력 데이터의 크기(N)가 증가함에 따라 알고리즘의 실행 시간이 얼마나 빠르게 증가하는지를 나타내는 척도입니다.

• 핵심: 실제로 걸리는 시간(밀리초)이 아니라, 연산 횟수를 N에 대한 함수로 표현하여 알고리즘의 효율성을 비교하는 데 중점을 둡니다.

 

2. 점근적 분석 (Asymptotic Analysis)

• 알고리즘의 최악의 경우(Worst-Case) 성능을 분석합니다. • N이 매우 커졌을 때 (점근적으로), 실행 시간에 가장 큰 영향을 미치는 최고차항만을 고려합니다. 상수는 무시합니다. ◦ 예: 5N^2 + 3N + 100 의 경우, N이 커질수록 5N^2이 지배적이므로 N^2만 고려합니다.

 

3. 빅 오 표기법 ({Big-O Notation, } O)

• 시간 복잡도를 나타내는 가장 일반적인 표기법입니다.

• 최악의 경우(Upper Bound) 실행 시간을 나타냅니다. 즉, 실행 시간이 이 값 이상으로 걸리지 않음을 보장합니다.

 

 📊 주요 시간 복잡도 종류 (Big-O)

빅 오 표기	이름	N에 따른 연산 횟수 증가	예시 알고리즘/연산	설명 (효율성 순)
O(1)	상수 시간	변화 없음 (상수)	배열/해시 테이블에서 특정 인덱스/키 접근	입력 크기에 관계없이 항상 일정한 시간이 걸립니다. 최고
O(log N)	로그 시간	N이 두 배 증가 시, 1회 연산 증가	이진 탐색 (Binary Search)	매우 효율적입니다. N이 커져도 연산 증가 폭이 매우 작습니다.
O(N)	선형 시간	N에 비례하여 증가	배열의 모든 요소를 순회하는 반복문	입력 크기에 정비례하여 시간이 걸립니다.
O(N log N)	선형 로그 시간	O(N)보다 약간 느림	병합 정렬 (Merge Sort), 힙 정렬 (Heap Sort)	효율적인 정렬 알고리즘에서 흔히 볼 수 있습니다.
O(N^2)	제곱 시간	N^2에 비례하여 증가	이중 반복문을 사용한 모든 쌍(Pair) 검사, 버블 정렬	입력 크기가 커지면 성능이 급격히 저하됩니다.
O(N^3)	세제곱 시간	N^3에 비례하여 증가	3중 반복문 (예: 행렬 곱셈)	입력 크기가 작을 때만 사용할 수 있습니다.
O(2^N)	지수 시간	기하급수적으로 증가	피보나치 수열의 재귀적 구현 (최적화 전)	N이 조금만 커져도 사실상 사용 불가능합니다.

 

🎯 코딩 테스트에서의 중요성

• 제한 시간: 코딩 테스트 문제에는 보통 **실행 시간 제한 (예: 1초)**이 있습니다. 일반적인 환경에서 1초는 대략 10^8 (1억) 번의 연산 횟수를 기준으로 합니다.

 

• N의 크기에 따른 선택: 문제에서 주어진 최대 입력 크기($N$)를 보고 어떤 시간 복잡도를 가진 알고리즘을 사용해야 통과할 수 있을지 판단해야 합니다.

 

최대 N	필요한 시간 복잡도
50	O(N^3), O(N^4), 또는 O(2^N)(작은 지수) 가능
2,000	O(N^2) 이하
100,000	O(N log N) 이하
10^7	O(N) 이하