알고리즘 복잡도와 Big-O 표기법의 핵심 개념 요약은 무엇인가요?

입력 크기(N)가 커질 때 알고리즘의 실행 시간(시간 복잡도)과 메모리 사용량(공간 복잡도)이 증가하는 비율을 수학적으로 분석하는 점근적 표기법을 학습합니다. 핵심 정리: Big-O 표기법은 최악의 경우(Worst Case) 연산 횟수의 점근적 상한을 나타내며, 상수 계수와 낮은 차수의 항은 모두 제거한다. 시간 복잡도 효율 순서는 O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!) 순이다. 탐색 범위가 매 단계 절반으로 줄어들거나 2배씩 건너뛰는 루프의 시간 복잡도는 O(log N)이다. 컴퓨터는 1초에 약 1억(10^8) 번 연산하므로, N = 100,000일 때는 O(N²)이 아닌 O(N log N) 이하의 알고리즘을 설계해야 한다.

개념 정리

글자

알고리즘 복잡도와 Big-O 표기법

Q: [알고리즘 복잡도와 Big-O 표기법 대표 예제] 다음 두 코드 조각 (A)와 (B)에 대해 입력 크기 N에 따른 시간 복잡도 Big-O를 각각 구하시오.

1) 코드 (A) 분석: 변수 i가 N에서 시작하여 매 반복마다 절반(1/2)으로 줄어듭니다: N → N/2 → N/4 → ... → N/(2^k) = 1. 양변에 2^k를 곱하고 로그를 취하면 k = log₂ N번 반복하므로 시간 복잡도는 O(log N)입니다. 2) 코드 (B) 분석: 바깥 루프는 1부터 N까지 총 N번 실행됩니다. 안쪽 루프는 j가 1, 2, 4, 8, ..., 2^k ≤ N으로 2배씩 커지므로 log₂ N번 실행됩니다. 서로 독립적인 두 루프가 중첩되어 있으므로 두 횟수를 곱하여 시간 복잡도는 O(N log N)이 됩니다.

단원 개요

입력 크기(N)가 커질 때 알고리즘의 실행 시간(시간 복잡도)과 메모리 사용량(공간 복잡도)이 증가하는 비율을 수학적으로 분석하는 점근적 표기법을 학습합니다.

선수 개념

필수 키워드:3가지 점근적 표기법Big-O (

O

, 점근적 상한)최악의 경우(Worst Case)Big-OBig-O 단순화 2대 법칙상수항과 계수는 모두 무시한다가장 빠르게 증가하는 최고차항만 남긴다

O(1)

(상수 시간)

O(\log N)

(로그 시간)절반(

1/2

)씩 줄어드는

이 단원의 내용

1점근적 표기법(Big-O, Big-Omega, Big-Theta)과 핵심 산출 규칙 2시간 복잡도 계층 순서와 대표 알고리즘 매핑 3코딩 테스트 실전: 제한 시간 1초와 입력 크기(N)별 알고리즘 선택법

점근적 표기법(Big-O, Big-Omega, Big-Theta)과 핵심 산출 규칙

알고리즘의 성능은 컴퓨터의 CPU 사양에 따라 측정 시간(초)이 달라지므로, 절대적인 시간이 아니라 입력 데이터 크기 $N$ 이 무한히 커질 때 기본 연산 횟수가 증가하는 추세로 평가합니다.

•

3가지 점근적 표기법:

Big-O ( $O$ , 점근적 상한): 최악의 경우(Worst Case)에도 연산 횟수가 이 함수보다 빠르게 증가하지 않음을 보장합니다 (실무와 코딩 테스트에서는 장애 방지를 위해 항상 최악 기준인 Big-O를 사용합니다).

Big-Omega ( $\Omega$ , 점근적 하한): 최선의 경우(Best Case) 최소 보장 연산 횟수입니다.

Big-Theta ( $\Theta$ , 점근적 상·하한 일치): 상한과 하한이 동일한 정확한 증가율입니다.

•

Big-O 단순화 2대 법칙:

상수항과 계수는 모두 무시한다:

T(N) = 5N + 100 \implies O(N)

(또한

O(2N)

이나

O(\frac{1}{2}N)

도 모두

O(N)

으로 표기).

가장 빠르게 증가하는 최고차항만 남긴다:

T(N) = 3N^2 + 50N \log N + 999 \implies O(N^2)

핵심 원리

1부터 N-1까지 더하는 이중 반복문(총 N(N-1)/2 = 0.5N² - 0.5N번 실행)의 시간 복잡도는 계수 0.5와 하위차항 -0.5N을 모두 버리고 깔끔하게 O(N²)이 됩니다.

시간 복잡도 계층 순서와 대표 알고리즘 매핑

$N$ 이 커질 때 효율적인(빠른) 순서부터 비효율적인(느린) 순서대로 나열하면 다음과 같습니다:

O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(N^3) < O(2^N) < O(N!)

•

$O(1)$ (상수 시간): 입력 크기

N

과 무관하게 즉시 완료 (배열 인덱스 접근, 해시 테이블 조회, 스택 Push/Pop).

•

$O(\log N)$ (로그 시간): 한 번 연산할 때마다 탐색 범위가 절반( $1/2$ )씩 줄어드는 알고리즘 (이진 탐색, 균형 이진 탐색 트리, 힙 삽입/삭제).

N = 10\text{억}(10^9)

이어도

\log_2(10^9) \approx 30

번 만에 끝납니다!

•

$O(N)$ (선형 시간): 데이터를 처음부터 끝까지 한 번 순회 (단일 for문, 선형 탐색, 최댓값/최솟값 찾기).

•

$O(N \log N)$ (선형 로그 시간): 데이터를 절반씩 분할(

\log N

층)하며 각 층에서

N

개씩 병합 처리 (병합 정렬, 퀵 정렬, 힙 정렬).

•

$O(N^2)$ (이차 시간): 중첩된 이중 for문 (버블·선택·삽입 정렬).

•

$O(2^N)$ / $O(N!)$ (지수 / 팩토리얼 시간): 부분집합 전체 탐색(

2^N

), 메모이제이션 없는 재귀 피보나치(

2^N

), 외판원 순회 TSP 모든 순열 탐색(

N!

풀이

1) 코드 (A) 분석:

변수 i가 N에서 시작하여 매 반복마다 절반(1/2)으로 줄어듭니다: N → N/2 → N/4 → ... → N/(2^k) = 1.

양변에 2^k를 곱하고 로그를 취하면 k = log₂ N번 반복하므로 시간 복잡도는 O(log N)입니다.

2) 코드 (B) 분석:

바깥 루프는 1부터 N까지 총 N번 실행됩니다.

안쪽 루프는 j가 1, 2, 4, 8, ..., 2^k ≤ N으로 2배씩 커지므로 log₂ N번 실행됩니다.

서로 독립적인 두 루프가 중첩되어 있으므로 두 횟수를 곱하여 시간 복잡도는 O(N log N)이 됩니다.

코딩 테스트 실전: 제한 시간 1초와 입력 크기(N)별 알고리즘 선택법

현대 채점 서버(CPU)는 1초에 약 $1\text{억}(10^8)$ 번의 단순 연산을 처리합니다. 문제에서 주어진 $N$ 의 최대 크기를 보면 어떤 시간 복잡도의 알고리즘을 설계해야 시간 초과(TLE)를 피할 수 있는지 즉시 역산할 수 있습니다.

•

$N \le 20$ :

O(2^N)

또는

O(N!)

가능 ➔ 백트래킹(Backtracking), 완전 탐색(Brute-force).

•

$N \le 500$ :

O(N^3)

가능 ➔ 플로이드-워셜(Floyd-Warshall), 3중 루프 DP.

•

$N \le 5,000$ :

O(N^2)

가능 ➔ 이중 for문, 2차원 동적 계획법(DP).

•

$N \le 100,000 \sim 1,000,000$ : 반드시 $O(N \log N)$ 또는 $O(N)$ 으로 풀어야 함! (

O(N^2)

사용 시

10^{10}

번 연산으로 100초가 걸려 무조건 시간 초과) ➔ 정렬, 이진 탐색, 투 포인터, 해시, 그리디, 다익스트라.

•

$N \ge 10^9$ (10억 이상):

O(N)

조차 시간 초과! 반드시 $O(\log N)$ (이진 탐색, 분할 정복 거듭제곱) 또는 $O(1)$ 수학 공식으로 풀어야 합니다.

학습 도움말

공간 복잡도(Space Complexity) 계산 팁: 4바이트 int형 배열 1,000만 개(10^7)는 약 40MB의 메모리를 차지합니다. 재귀 함수를 너무 깊게 호출하면 스택 프레임이 누적되어 메모리 제한이나 최대 재귀 깊이(Python 기본 1,000)를 초과하므로 공간 복잡도 역시 함께 체크해야 합니다.

핵심 요약

✓
Big-O 표기법은 최악의 경우(Worst Case) 연산 횟수의 점근적 상한을 나타내며, 상수 계수와 낮은 차수의 항은 모두 제거한다.
✓
시간 복잡도 효율 순서는 O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!) 순이다.
✓
탐색 범위가 매 단계 절반으로 줄어들거나 2배씩 건너뛰는 루프의 시간 복잡도는 O(log N)이다.
✓
컴퓨터는 1초에 약 1억(10^8) 번 연산하므로, N = 100,000일 때는 O(N²)이 아닌 O(N log N) 이하의 알고리즘을 설계해야 한다.

알고리즘 복잡도와 Big-O 표기법

점근적 표기법(Big-O, Big-Omega, Big-Theta)과 핵심 산출 규칙

시간 복잡도 계층 순서와 대표 알고리즘 매핑

코딩 테스트 실전: 제한 시간 1초와 입력 크기(N)별 알고리즘 선택법

핵심 요약

설명 다음에는 직접 풀어 보세요

알고리즘 복잡도와 Big-O 표기법 단원 연습 문제

참고 근거와 확인 범위