빅오 표기법은 알고리즘의 성능을 입력 크기 n에 따라 비교하는 기준입니다. 실제 실행 시간보다 입력이 커질 때 증가하는 속도에 집중하므로, 복잡한 코드도 핵심 반복 구조만 보면 대략적인 효율을 판단할 수 있습니다.
📌 핵심 5줄 요약
1. 입력 크기 n이 커질 때 연산 횟수가 어떻게 증가하는지를 나타내는 표기법이 빅오 표기법입니다.
2. 일반적으로 O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 순서로 입력 증가에 따른 부담이 커집니다.
3. 반복문이 하나라고 무조건 O(n)은 아니며, 반복 횟수와 중첩 구조를 함께 확인해야 합니다.
4. 빅오는 상수와 낮은 차수 항을 생략하므로 실제 실행 시간이 항상 정확히 일치한다는 뜻은 아닙니다.
5. 알고리즘을 고를 때는 시간복잡도뿐 아니라 공간복잡도, 입력 조건, 데이터 특성도 함께 확인해야 합니다.
📌 목차
01 | 빅오 표기법의 의미
02 | 입력 크기 n과 증가율
03 | O(1) 상수 시간
04 | O(log n) 로그 시간
05 | O(n) 선형 시간
06 | O(n log n) 선형 로그 시간
07 | O(n²) 이차 시간
08 | 지수 시간과 팩토리얼 시간
09 | 알고리즘 시간복잡도 비교
10 | 반복문으로 복잡도 계산하기
11 | 조건문과 여러 구문의 복잡도
12 | 재귀 알고리즘의 복잡도
13 | 시간복잡도와 공간복잡도
14 | 코딩테스트에서 활용하는 방법
01 | 빅오 표기법의 의미
빅오 표기법은 알고리즘의 최악의 경우 또는 입력 크기에 따른 증가율을 간결하게 표현하는 방법입니다. 여기서 n은 배열의 원소 수, 문자열의 길이, 그래프의 정점 수처럼 문제의 규모를 나타내는 변수입니다.
예를 들어 배열의 모든 원소를 한 번씩 확인한다면 입력이 10개일 때 10번, 1,000개일 때 1,000번에 가까운 연산이 필요하므로 O(n)으로 표현합니다. 정확한 실행 시간은 컴퓨터와 언어에 따라 달라지지만 증가율은 비교할 수 있습니다.
02 | 입력 크기 n과 증가율
빅오에서 가장 중요한 것은 특정 입력 하나의 속도가 아니라 n이 커질 때 작업량이 얼마나 빠르게 증가하는가입니다. O(n)과 O(n²)은 작은 입력에서는 차이가 작아 보일 수 있지만, 입력이 커지면 필요한 연산량의 증가 폭이 크게 달라집니다.
또한 빅오는 상수 계수를 보통 생략합니다. 3n과 100n은 모두 O(n)입니다. 둘의 실제 속도가 같다는 뜻이 아니라, 입력 크기에 따른 성장 형태가 선형이라는 의미입니다.
03 | O(1) 상수 시간
O(1)은 입력 크기와 관계없이 일정한 횟수의 작업을 수행하는 경우입니다. 배열에서 인덱스로 특정 원소를 읽거나, 변수 두 개의 값을 비교하는 작업이 대표적입니다.
다만 O(1)이 항상 가장 빠른 실제 실행 시간을 보장하는 것은 아닙니다. 해시 테이블 조회처럼 평균적으로 O(1)인 작업도 충돌이나 구현 방식에 따라 달라질 수 있으므로, 표기에서 평균·최악 조건을 함께 확인해야 합니다.
04 | O(log n) 로그 시간
O(log n)은 한 번의 처리마다 문제의 범위가 일정한 비율로 줄어드는 경우에 나타납니다. 정렬된 배열에서 중간값과 비교하며 탐색 범위를 절반씩 줄이는 이진 탐색이 대표적입니다.
n개의 데이터를 매번 절반으로 줄이면 필요한 단계 수는 대략 log₂n입니다. 따라서 데이터가 크게 늘어도 작업 단계가 비교적 천천히 증가합니다. 이진 탐색을 사용하려면 데이터가 정렬되어 있거나 탐색 조건을 유지하는 구조여야 합니다.
05 | O(n) 선형 시간
O(n)은 입력 원소를 한 번씩 확인하는 알고리즘에서 흔히 나타납니다. 배열의 최댓값 찾기, 전체 합 계산, 특정 조건을 만족하는 원소의 개수 세기가 이에 해당합니다.
순차 탐색은 원하는 값을 찾으면 중간에 종료할 수 있어 최선의 경우 O(1)이지만, 값이 없거나 마지막에 있으면 모든 원소를 확인해야 합니다. 따라서 최악의 시간복잡도는 O(n)으로 판단합니다.
06 | O(n log n) 선형 로그 시간
O(n log n)은 데이터를 여러 단계로 나누거나 정렬하는 알고리즘에서 자주 볼 수 있습니다. 대표적으로 병합 정렬이 있으며, 데이터를 log n개의 단계로 나누고 각 단계에서 전체 원소에 가까운 작업을 수행합니다.
효율적인 비교 기반 정렬 알고리즘의 일반적인 복잡도로 자주 사용되며, O(n²) 정렬보다 큰 입력에서 유리합니다. 다만 실제 속도는 메모리 접근 방식, 재귀 호출, 데이터가 이미 정렬되어 있는지 등에 따라 달라질 수 있습니다.
07 | O(n²) 이차 시간
O(n²)은 입력을 두 겹의 반복문으로 비교하는 상황에서 흔히 발생합니다. 모든 원소 쌍을 확인하거나, 배열의 각 원소를 다른 모든 원소와 비교하는 문제가 예입니다.
버블 정렬과 선택 정렬은 대표적으로 O(n²) 복잡도를 가집니다. 작은 데이터에서는 구현이 단순하다는 장점이 있지만, 입력이 커지면 반복 횟수가 급격히 늘어나므로 더 효율적인 방법을 검토해야 합니다.
08 | 지수 시간과 팩토리얼 시간
O(2ⁿ)은 입력이 하나 증가할 때 가능한 경우의 수가 배로 늘어나는 알고리즘에서 나타납니다. 모든 부분집합을 확인하거나, 메모이제이션 없이 일부 재귀 문제를 해결할 때 대표적으로 발생합니다.
O(n!)은 모든 순열을 확인하는 경우처럼 입력 원소의 순서를 모두 시도할 때 나타납니다. 두 복잡도는 입력이 조금만 커져도 연산량이 빠르게 증가하므로, 가지치기, 동적 계획법, 그리디 알고리즘 등으로 탐색 범위를 줄일 수 있는지 확인해야 합니다.
09 | 알고리즘 시간복잡도 비교
주요 시간복잡도는 아래처럼 비교할 수 있습니다. 일반적인 성장률 기준으로 왼쪽에 있는 복잡도일수록 큰 입력에 유리합니다.
| 시간복잡도 | 대표적인 상황 | 특징 |
|---|---|---|
| O(1) | 배열 인덱스 접근 | 입력 크기와 무관 |
| O(log n) | 이진 탐색 | 범위를 반복해서 축소 |
| O(n) | 순차 탐색, 전체 합 계산 | 원소를 한 번씩 확인 |
| O(n log n) | 병합 정렬 | 정렬에 자주 사용 |
| O(n²) | 버블 정렬, 모든 쌍 비교 | 중첩 반복문에서 흔함 |
| O(2ⁿ) | 부분집합 전수 탐색 | 입력 증가에 매우 민감 |
| O(n!) | 순열 전수 탐색 | 가장 빠르게 증가하는 편 |
이 표는 성장률을 단순 비교한 것입니다. 실제 알고리즘 선택에서는 입력 제한과 구현 비용을 반드시 함께 봐야 합니다.
10 | 반복문으로 복잡도 계산하기
반복문을 분석할 때는 반복 횟수를 먼저 세면 됩니다. 하나의 반복문이 n번 실행되면 O(n)입니다. 서로 이어진 반복문 두 개가 각각 n번 실행되면 O(n+n)이지만, 상수와 항을 정리해 O(n)으로 표현합니다.
반면 반복문 안에 또 다른 n회 반복문이 있으면 n×n이 되어 O(n²)입니다. 안쪽 반복 횟수가 항상 n이 아니라 절반, 두 배, 또는 특정 조건에 따라 변한다면 실제 증가 형태를 따로 계산해야 합니다.
반복문 분석 예시
바깥 반복문이 n번 실행되고 안쪽 반복문이 매번 n번 실행되면 전체 작업은 n²에 비례합니다. 바깥 반복문이 실행될 때마다 값을 두 배로 만든다면 반복 횟수는 log n에 가까워져 O(log n)이 될 수 있습니다.
11 | 조건문과 여러 구문의 복잡도
조건문 자체는 복잡도를 결정하지 않습니다. 조건 안에서 실행되는 작업량이 핵심입니다. if와 else 중 하나만 실행되고 각 블록이 O(n)이라면 전체 복잡도는 보통 O(n)으로 봅니다.
여러 구문이 순서대로 실행될 때는 복잡도를 더한 뒤 가장 빠르게 증가하는 항을 남깁니다. O(n²)+O(n)+O(1)은 O(n²)입니다. 다만 조건에 따라 서로 다른 경로가 실행되므로 최선, 평균, 최악의 경우가 달라질 수 있습니다.
12 | 재귀 알고리즘의 복잡도
재귀 함수는 함수가 몇 번 호출되고 각 호출에서 어떤 작업을 수행하는지 확인해야 합니다. 한 번 호출될 때 입력이 절반으로 줄어드는 구조는 O(log n)과 관련이 있고, 두 개 이상의 재귀 호출이 반복적으로 발생하면 지수 시간이 될 가능성이 있습니다.
같은 하위 문제를 여러 번 계산하는 재귀는 비효율적일 수 있습니다. 이미 계산한 결과를 저장하는 메모이제이션이나 동적 계획법을 적용하면 중복 계산을 줄이고 시간복잡도를 개선할 수 있습니다.
13 | 시간복잡도와 공간복잡도
시간복잡도는 실행에 필요한 연산량의 증가율이고, 공간복잡도는 입력 공간을 제외하거나 포함하는 기준에 따라 알고리즘이 사용하는 메모리 증가율을 나타냅니다.
예를 들어 반복문으로 배열을 한 번 처리하는 방식은 추가 메모리 O(1)을 사용할 수 있지만, 결과를 별도 배열에 저장하면 추가 공간 O(n)이 필요할 수 있습니다. 실행 시간을 줄이기 위해 메모리를 더 사용하는 경우도 있으므로 두 기준을 함께 비교해야 합니다.
14 | 코딩테스트에서 활용하는 방법
문제를 풀기 전 먼저 입력 크기와 시간 제한을 확인합니다. 입력이 매우 큰데 O(n²) 풀이를 사용하면 시간 초과 가능성이 있으므로, 정렬·해시·이진 탐색·투 포인터·누적 합·동적 계획법 같은 방법으로 반복 작업을 줄일 수 있는지 살펴봅니다.
실전 판단 순서
첫째, 입력 데이터의 개수를 n으로 정의합니다. 둘째, 가장 많이 반복되는 부분을 찾습니다. 셋째, 중첩 반복문과 재귀 호출 구조를 확인합니다. 넷째, 최악의 경우를 기준으로 복잡도를 계산합니다. 마지막으로 시간복잡도뿐 아니라 필요한 메모리와 자료구조의 조건을 검토합니다.
예를 들어 정렬된 배열에서 값을 찾는 문제라면 처음부터 끝까지 확인하는 O(n) 방식과 중간값을 기준으로 범위를 줄이는 O(log n) 방식을 비교할 수 있습니다. 단, 이진 탐색은 정렬 상태가 유지되어야 하므로 정렬 비용까지 포함해야 하는 상황인지도 확인해야 합니다.
☑ 체크리스트
- 입력 크기 n이 무엇인지 먼저 정의했는가?
- 가장 많이 반복되는 코드 구간을 찾았는가?
- 중첩 반복문의 각 반복 횟수를 따로 계산했는가?
- 최선·평균·최악의 경우를 구분했는가?
- 정렬이나 자료구조 준비에 필요한 비용을 포함했는가?
- 추가 배열이나 재귀 호출로 공간복잡도가 커지지 않는가?
📖 자주하는 질문 Q&A
빅오 표기법에서 상수를 생략하는 이유는 무엇인가요?
입력 크기가 커질수록 상수보다 증가율의 차이가 성능에 더 큰 영향을 주기 때문입니다. 다만 실제 실행 시간에서는 상수와 하드웨어, 언어, 구현 방식도 영향을 주므로 O(n)이 같은 모든 알고리즘이 실제로 같은 속도라는 뜻은 아닙니다.
반복문이 두 개면 항상 O(n²)인가요?
아닙니다. 두 반복문이 서로 독립적으로 이어져 있다면 O(n+n)=O(n)일 수 있습니다. 한 반복문이 다른 반복문 안에 들어가고 두 반복 횟수가 모두 n에 비례할 때 O(n²)으로 판단합니다.
평균 시간복잡도와 최악 시간복잡도 중 무엇을 봐야 하나요?
문제의 요구 조건과 알고리즘의 특성에 따라 다르지만, 입력이 어떤 형태로 주어져도 안전해야 한다면 최악의 경우를 우선 확인하는 것이 좋습니다. 평균 시간복잡도를 사용할 때는 평균이 성립하는 조건도 함께 살펴야 합니다.
O(n log n)이 O(n²)보다 항상 빠른가요?
입력이 충분히 커질수록 일반적으로 O(n log n)이 유리합니다. 그러나 입력이 작거나 상수 비용이 큰 구현이라면 실제 실행 시간은 달라질 수 있으므로, 복잡도는 알고리즘의 성장률을 비교하는 기준으로 활용해야 합니다.
📝 마무리
빅오 표기법은 알고리즘이 입력 증가에 따라 얼마나 빠르게 부담이 커지는지 비교하는 도구입니다. 반복문, 재귀 호출, 정렬과 탐색 구조를 기준으로 O(1)부터 O(n!), 시간복잡도와 공간복잡도까지 함께 분석하면 문제에 맞는 알고리즘을 더 합리적으로 선택할 수 있습니다.