함께 배우는 수업 · 컴퓨터/정보

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

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

이 수업에서 해 볼 일

입력 크기에 따른 연산 수의 증가율을 비교한다

먼저 알면 좋은 것: 다항함수, 지수함수($2^N$), 로그함수($\log_2 N$)의 그래프 증가율 · 반복문(for, while)의 중첩 실행 횟수 계산 · 수열의 합($\sum_{k=1}^{N} k = \frac{N(N+1)}{2}$) 공식

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

복잡도는 입력 크기가 커질 때 작업 수가 얼마나 빨리 늘어나는지 나타낸다. 순차 실행은 비용을 더하고, 중첩 반복은 각 반복 횟수를 곱해 세어 보자.n번 작업 뒤 다시 n번 작업하면 2n이다. 반면 n개의 항목 각각에 n번 작업하면 n²이다. 상수 배를 생략해도 이 두 증가율의 차이는 남는다.Big-O만으로 특정 컴퓨터의 실행 시간을 확정할 수는 없다. 다만 큰 입력에서의 확장성을 비교하는 근거가 되며, 이진 탐색처럼 후보를 일정 비율로 줄이면 로그 단계가 생긴다.

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

알고리즘의 성능은 컴퓨터의 CPU 사양에 따라 측정 시간(초)이 달라지므로, 절대적인 시간이 아니라 입력 데이터 크기 $N$ 이 무한히 커질 때 기본 연산 횟수가 증가하는 추세로 평가합니다. - 3가지 점근적 표기법: 1. Big-O ( $O$ , 점근적 상한): 최악의 경우(Worst Case)에도 연산 횟수가 이 함수보다 빠르게 증가하지 않음을 보장합니다 (실무와 코딩 테스트에서는 장애 방지를 위해 항상 최악 기준인 Big-O를 사용합니다). 2. Big-Omega ( $\Omega$ , 점근적 하한): 최선의 경우(Best Case) 최소 보장 연산 횟수입니다. 3. Big-Theta ( $\Theta$ , 점근적 상·하한 일치): 상한과 하한이 동일한 정확한 증가율입니다. - Big-O 단순화 2대 법칙: 1. 상수항과 계수는 모두 무시한다:

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

(또한

O(2N)

이나

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

도 모두

O(N)

으로 표기). 2. 가장 빠르게 증가하는 최고차항만 남긴다:

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²)이 됩니다.

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

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!

예제로 살펴보기

다음 두 코드 조각 (A)와 (B)에 대해 입력 크기 N에 따른 시간 복잡도 Big-O를 각각 구하시오. (A) i = N; while (i > 1) { i = i // 2; } (B) 바깥 루프는 i가 1부터 N까지 1씩 증가하고(for i in range(N)), 안쪽 루프는 j가 1부터 N까지 2배씩 증가(j = j * 2)하는 이중 루프

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)이 됩니다.

확인: Big-O 표기법은 최악의 경우(Worst Case) 연산 횟수의 점근적 상한을 나타내며, 상수 계수와 낮은 차수의 항은 모두 제거한다.

3. 코딩 테스트 실전: 제한 시간 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)를 초과하므로 공간 복잡도 역시 함께 체크해야 합니다.

참고 근거와 확인 범위

Harvard CS50 · Lecture 3: Algorithms ↗
입력 크기에 따른 실행 시간과 Big-O

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →