[알고리즘] 02. 시간복잡도와 Big-O 쉽게 이해하기

[알고리즘] 02. 시간복잡도와 Big-O 쉽게 이해하기

지난 글에서는 알고리즘이 문제를 해결하기 위한 순서라고 정리했습니다. 이번 글에서는 알고리즘을 공부할 때 거의 반드시 나오는 개념인 시간복잡도와 Big-O에 대해 알아보겠습니다.

처음에는 이름부터 어렵게 느껴질 수 있습니다. 하지만 핵심은 단순합니다.

시간복잡도는 입력값이 많아질 때, 코드가 얼마나 오래 걸릴지 대략 판단하는 기준입니다.

---

1. 시간복잡도가 필요한 이유

코드는 결과만 맞으면 끝이라고 생각하기 쉽습니다. 하지만 알고리즘 문제에서는 정답이 맞는 것만큼 시간 안에 실행되는 것도 중요합니다.

예를 들어 회원이 10명일 때는 어떤 방식으로 찾아도 크게 차이가 나지 않습니다. 하지만 회원이 10만 명, 100만 명이 되면 이야기가 달라집니다.

• 10명 중에서 찾기
• 10만 명 중에서 찾기
• 100만 명 중에서 찾기

입력 데이터가 커질수록 비효율적인 코드는 점점 느려집니다. 시간복잡도는 이런 차이를 미리 판단하기 위해 사용합니다.

---

2. 시간복잡도는 정확한 실행 시간이 아닙니다

시간복잡도는 코드가 정확히 몇 초 걸리는지를 의미하지 않습니다. 컴퓨터 성능, 언어, 실행 환경에 따라 실제 시간은 달라질 수 있기 때문입니다.

대신 시간복잡도는 입력 크기가 증가할 때 연산 횟수가 어떻게 늘어나는지를 봅니다.

예를 들어 입력값의 개수를 N이라고 할 때, N이 커질수록 코드의 반복 횟수가 어떻게 변하는지를 보는 것입니다.

시간복잡도는 실제 초 단위 시간이 아니라, 입력 크기에 따른 연산 증가 흐름을 보는 개념입니다.

---

3. Big-O 표기법이란?

Big-O 표기법은 알고리즘의 효율을 표현하는 방식입니다. 보통 O( ) 형태로 작성합니다.

대표적인 Big-O 표기는 다음과 같습니다.

표기	이름	느낌
O(1)	상수 시간	입력 크기와 상관없이 거의 일정
O(log N)	로그 시간	매우 빠른 편
O(N)	선형 시간	입력 개수만큼 증가
O(N log N)	선형 로그 시간	효율적인 정렬에서 자주 등장
O(N²)	제곱 시간	입력이 커질수록 급격히 느려짐

처음에는 모든 표기를 외우려고 하기보다, 반복문이 몇 번 도는지를 기준으로 이해하는 것이 좋습니다.

---

4. O(1) — 입력 크기와 상관없는 경우

O(1)은 입력 데이터가 많아져도 실행 횟수가 거의 변하지 않는 경우입니다.

int[] arr = {10, 20, 30, 40, 50};

System.out.println(arr[0]);

위 코드는 배열의 첫 번째 값을 바로 출력합니다. 배열에 값이 5개 있든, 500개 있든, 첫 번째 값에 접근하는 동작은 한 번입니다.

이런 경우 시간복잡도는 O(1)입니다.

---

5. O(N) — 입력 개수만큼 반복하는 경우

O(N)은 입력 개수만큼 반복하는 경우입니다. 가장 많이 볼 수 있는 형태입니다.

int[] arr = {10, 20, 30, 40, 50};

for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

배열에 값이 5개 있으면 5번 반복하고, 100개 있으면 100번 반복합니다.

입력 개수 N에 비례해서 실행 횟수가 증가하므로 시간복잡도는 O(N)입니다.

---

6. O(N²) — 반복문 안에 반복문이 있는 경우

O(N²)은 반복문 안에 또 반복문이 있는 경우 자주 등장합니다.

int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        System.out.println(arr[i] + ", " + arr[j]);
    }
}

바깥 반복문이 N번 돌고, 안쪽 반복문도 매번 N번 돕니다.

그래서 전체 반복 횟수는 대략 N × N이 됩니다. 이런 경우 시간복잡도는 O(N²)입니다.

N이 작을 때는 괜찮아 보이지만, N이 커질수록 실행 횟수가 빠르게 증가합니다.

N	N²
10	100
100	10,000
1,000	1,000,000
10,000	100,000,000

이처럼 중첩 반복문은 입력 크기가 커질수록 부담이 커지기 때문에 주의해야 합니다.

---

7. 시간복잡도에서 작은 숫자는 보통 생략합니다

Big-O에서는 가장 큰 흐름만 중요하게 봅니다. 그래서 작은 상수나 덜 중요한 항은 보통 생략합니다.

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

위 코드는 반복문이 두 개 있으므로 실제로는 약 2N번 실행됩니다. 하지만 Big-O에서는 상수 2를 생략해서 O(N)이라고 표현합니다.

마찬가지로 O(N + 10)도 큰 흐름에서는 O(N)으로 봅니다.

Big-O는 정확한 실행 횟수보다, 입력이 커질 때 증가하는 큰 흐름을 봅니다.

---

8. 시간복잡도를 빠르게 판단하는 방법

처음에는 아래 기준으로 판단하면 좋습니다.

• 반복문이 없고 바로 처리하면 O(1)
• 반복문이 한 번 전체를 돌면 O(N)
• 반복문 안에 반복문이 있으면 O(N²)
• 데이터를 절반씩 줄이면 O(log N)
• 정렬 알고리즘은 보통 O(N log N)

물론 문제에 따라 더 복잡한 경우도 있지만, 처음에는 이 정도 기준만 알아도 대부분의 기초 문제를 이해하는 데 도움이 됩니다.

---

9. 알고리즘 문제에서 시간복잡도 보는 법

알고리즘 문제를 풀 때는 입력 제한을 꼭 확인해야 합니다. 입력 개수에 따라 가능한 풀이가 달라지기 때문입니다.

입력 크기	가능한 시간복잡도 예시
N ≤ 100	O(N²), O(N³)도 가능할 수 있음
N ≤ 10,000	O(N²)은 조심해야 함
N ≤ 100,000	O(N log N), O(N) 권장
N ≤ 1,000,000	O(N) 또는 O(log N) 위주

입력 크기가 큰데 중첩 반복문을 사용하면 시간 초과가 발생할 수 있습니다. 그래서 문제를 풀기 전 입력 제한을 보고 풀이 방식을 정하는 습관이 필요합니다.

---

10. 정리

이번 글에서는 시간복잡도와 Big-O 표기법을 정리했습니다.

• 시간복잡도는 입력 크기에 따라 실행 횟수가 얼마나 증가하는지 보는 기준이다.
• Big-O는 알고리즘의 효율을 표현하는 표기법이다.
• O(1)은 입력 크기와 상관없이 거의 일정하다.
• O(N)은 입력 개수만큼 실행된다.
• O(N²)은 중첩 반복문에서 자주 나타난다.
• 입력 제한을 보고 가능한 알고리즘을 선택해야 한다.

알고리즘 문제를 풀 때 시간복잡도는 선택이 아니라 기본입니다. 처음에는 어렵게 느껴져도 반복문이 몇 번 도는지부터 차근차근 확인하면 충분히 익숙해질 수 있습니다.

코드가 맞는 것과 시간 안에 통과하는 것은 다릅니다. 시간복잡도는 그 차이를 판단하는 기준입니다.

---

다음 글 예고

다음 글에서는 공간복잡도에 대해 알아보겠습니다.

시간만큼 중요한 것이 메모리입니다. 다음 글에서는 코드가 실행될 때 메모리를 얼마나 사용하는지 판단하는 방법을 정리하겠습니다.