---
title: "빅오 표기법: 입력이 커질 때 계산량은 어떻게 늘어날까"
author: "Lee"
published_at: "2026-10-18T15:13:02.000Z"
updated_at: "2026-09-30T09:25:22.573Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95-%EC%9E%85%EB%A0%A5%EC%9D%B4-%EC%BB%A4%EC%A7%88-%EB%95%8C-%EA%B3%84%EC%82%B0%EB%9F%89%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EB%8A%98%EC%96%B4%EB%82%A0%EA%B9%8C"
ai_assisted: false
---

# 빅오 표기법: 입력이 커질 때 계산량은 어떻게 늘어날까

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95-%EC%9E%85%EB%A0%A5%EC%9D%B4-%EC%BB%A4%EC%A7%88-%EB%95%8C-%EA%B3%84%EC%82%B0%EB%9F%89%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EB%8A%98%EC%96%B4%EB%82%A0%EA%B9%8C)

같은 문제를 푸는 프로그램도 입력이 커지면 전혀 다른 모습을 보인다. 원소가 열 개일 때는 차이가 작지만 백만 개가 되면 한쪽은 끝나고 다른 쪽은 오래 기다리게 한다. 점근적 표기법은 이런 증가 양상을 입력 크기 n의 함수로 설명한다. 특정 컴퓨터에서 측정한 초 단위 시간보다 알고리즘의 구조를 비교하는 데 초점을 둔다.

![상수·로그·선형·선형로그·제곱 함수의 성장률을 비교한 개념 그래프](/api/v1/media/e948dfdb-5286-4b53-bf09-53d428773124)

*대표 함수의 성장률 비교로, 실제 실행 시간을 측정한 그래프는 아니다.*

### O, Ω, Θ가 말하는 것

f(n)=O(g(n))은 충분히 큰 모든 n에서 f(n)이 어떤 양의 상수 c를 곱한 g(n) 이하라는 뜻이다. Ω는 같은 방식의 하한이고, Θ는 상한과 하한을 함께 만족한다. 따라서 Θ(n²)인 함수는 O(n²)이면서 O(n³)이기도 하다. 빅오는 꼭 가장 빡빡한 증가율을 뜻하지 않는다.

예를 들어 3n²+10n+7이라는 연산 수를 얻었다면 n이 커질수록 n² 항이 지배한다. 상수배와 낮은 차수 항을 숨겨 Θ(n²)이라고 표현할 수 있다. 이를 실제 시간 3n²초라는 의미로 읽으면 잘못이다. 하드웨어, 언어, 메모리 배치에 따른 상수는 남아 있다.

### 연산을 어떻게 세는가

길이 n 배열을 한 번 훑고 각 원소에 일정한 작업을 하면 Θ(n)이다. 두 반복문이 각각 n번 독립적으로 돌면 Θ(n²)이다. 하지만 안쪽 반복문이 매번 절반의 범위만 탐색하거나 포인터가 전체 실행 중 n번만 이동한다면 코드의 반복문 개수만으로 판단할 수 없다. 실제 수행 횟수를 합산해야 한다.

정렬된 배열의 이진 탐색은 한 비교 뒤 후보 범위를 절반으로 줄인다. n/2ᵏ가 1 정도가 되는 k는 log₂n이므로 비교 횟수는 O(log n)이다. n이 두 배가 되어도 필요한 단계는 대략 한 번 늘어난다. 선형 탐색과는 증가 방식이 다르다.

시간 복잡도에는 어떤 경우를 분석했는지도 붙어야 한다. 최악의 입력을 기준으로 한 O(n), 입력 분포를 가정한 평균 O(n), 연속 연산의 비용을 합친 분할 상환 O(1)은 서로 다른 주장이다. 빅오라는 표기 자체가 자동으로 최악의 경우를 의미하지 않는다.

공간도 같은 방법으로 센다. 입력 배열을 제외한 추가 저장소를 셀지 전체 메모리를 셀지 먼저 정하고, 재귀 호출 스택도 포함한다. 큰 입력에서 성장률은 중요한 기준이지만 작은 입력의 실행 속도, 구현 난도, 캐시 효율까지 대신 판단해 주지는 않는다.

### 같은 입력에서 두 절차를 비교하면

다음 코드는 값이 같은 원소 쌍의 수를 세는 단순한 절차다. 배열 조회와 고정 크기 값의 비교를 일정 비용으로 가정한다. 조건이 참인지와 무관하게 모든 서로 다른 인덱스 쌍을 검사한다.

```python
def count_equal_pairs(values):
    number_of_pairs = 0
    input_size = len(values)
    for first_index in range(input_size):
        for second_index in range(first_index + 1, input_size):
            if values[first_index] == values[second_index]:
                number_of_pairs += 1
    return number_of_pairs
```

비교 횟수는 (n-1)+(n-2)+…+1=n(n-1)/2다. n=100이면 4,950번, n=1,000이면 499,500번으로 입력이 열 배일 때 작업량은 거의 백 배가 된다. 이에 비해 배열 한 번 순회는 100번에서 1,000번으로 열 배 증가한다. 이 수치가 서로 다른 성장률을 체감하게 한다. 결과를 저장하는 변수는 일정 개수라 추가 공간은 O(1)이다. 시간 Θ(n²)와 공간 O(1)은 함께 성립할 수 있다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)