입력이 커지면 알고리즘은 얼마나 느려질까? | 1-SUM부터 Tilde, Big-O, Big-Ω까지

알고리즘을 작성하는 것만큼 중요한 것이 있다.

이 알고리즘은 입력 데이터가 많아졌을 때도 사용할 수 있을까?

데이터가 10개일 때 잘 동작하는 것과 데이터가 100만 개일 때 잘 동작하는 것은 전혀 다른 문제다.

그래서 알고리즘을 분석할 때는 단순히 "내 컴퓨터에서 몇 초 걸렸다"가 아니라 입력 크기 N이 증가함에 따라 필요한 연산의 수가 어떻게 증가하는가를 살펴본다.

이번 장에서는 이를 1-SUM과 2-SUM부터 시작해서 생각해본다.

---

1. 왜 알고리즘을 분석할까?

두 알고리즘이 있다고 생각해보자.

알고리즘 A → N²번 정도 연산
알고리즘 B → N log N번 정도 연산

N이 작을 때는 둘의 차이가 크게 느껴지지 않을 수 있다.

하지만 N이 커지면 상황이 달라진다.

예를 들어

N = 1,000,000

이라면

N²
= 1,000,000,000,000

N log₂N
≈ 1,000,000 × 20
≈ 20,000,000

정도가 된다.

같은 문제를 해결하더라도 알고리즘의 성장 속도에 따라 필요한 연산량이 엄청나게 달라질 수 있다.

그래서 알고리즘 분석에서는 입력 크기 N에 따른 실행 시간과 메모리의 증가량을 중요하게 본다.

---

2. 가장 간단한 예제: 1-SUM

다음 코드가 있다고 하자.

int count = 0;

for (int i = 0; i < N; i++) {

    if (a[i] == 0) {
        count++;
    }
}

이 알고리즘은 배열을 처음부터 끝까지 한 번 확인하면서 값이 0인 원소의 개수를 센다.

예를 들어

[-3, 0, 5, 0, 7]

이라면

-3 → 확인
 0 → 확인 → count++
 5 → 확인
 0 → 확인 → count++
 7 → 확인

총 N개의 원소를 확인한다.

따라서 직관적으로 생각하면 실행되는 연산의 수가 N에 비례한다.

하지만 강의에서는 여기서 바로 O(N)이라고 끝내지 않고 실제로 어떤 명령이 몇 번 실행되는지 먼저 계산한다.

---

3. 1-SUM의 명령 횟수를 직접 세어보자

코드를 다시 보자.

int count = 0;

for (int i = 0; i < N; i++) {

    if (a[i] == 0) {
        count++;
    }
}

여기에는 여러 연산이 존재한다.

변수 선언
대입
i < N 비교
a[i] 접근
a[i] == 0 비교
i++
count++

예를 들어 i < N은 반복문이 종료되는 마지막 검사까지 포함하기 때문에 대략

N + 1번

실행된다.

a[i] 접근과 a[i] == 0 비교는 각 원소마다 이루어지므로

N번

이다.

반면

count++;

는 배열에 실제로 0이 몇 개 있는지에 따라 달라진다.

최소 0번
최대 N번

실행될 수 있다.

중요한 것은 세부적인 횟수가 조금씩 달라도 전체적으로 보면 N에 비례해서 증가하는 연산들이 지배적이라는 것이다.

그래서 1-SUM은 linear한 성장 형태를 가진다.

---

4. 2-SUM은 무엇일까?

이번에는 배열에서 서로 다른 두 원소를 선택해서 합이 0이 되는 조합을 찾는다고 하자.

예를 들어

[-10, -5, 0, 5, 10]

이라면

(-10, 10)
(-5, 5)

가 존재한다.

Brute Force 방식으로 구현하면 다음과 같은 구조가 된다.

int count = 0;

for (int i = 0; i < N; i++) {

    for (int j = i + 1; j < N; j++) {

        if (a[i] + a[j] == 0) {
            count++;
        }
    }
}

여기서 중요한 것은

j = i + 1

이다.

왜 j = 0부터 시작하지 않을까?

같은 원소를 자기 자신과 비교할 필요가 없고,

a[0] + a[1]

을 확인했다면 나중에

a[1] + a[0]

을 다시 확인할 필요도 없기 때문이다.

즉 중복되지 않는 두 원소의 조합만 검사한다.

---

5. 두 원소를 고르는 경우의 수

N개의 데이터 중에서 서로 다른 2개를 선택하는 경우의 수는

N choose 2

이다.

수식으로 표현하면

N(N - 1)
────────
   2

이다.

왜 그런지 반복문으로 생각하면 더 쉽다.

첫 번째 i에서는

N - 1

개를 비교한다.

그다음에는

N - 2

개.

계속하면

(N - 1) + (N - 2) + ... + 2 + 1

이 된다.

결과는

N(N - 1) / 2

이다.

전개하면

1/2 N² - 1/2 N

이 된다.

여기서부터 알고리즘 분석에서 중요한 질문이 생긴다.

매번 1/2 N² - 1/2 N처럼 정확하게 써야 할까?

---

6. 정확한 명령 횟수를 계속 계산하는 것은 번거롭다

실제 프로그램에서는 비교뿐 아니라 대입, 배열 접근, 증가 연산 등 다양한 연산이 발생한다.

그래서 정확하게 계산하면 실행 횟수가 다음처럼 나올 수 있다.

1/2 N² + 3N + 7

혹은

2N² + 5N + 10

처럼 복잡해질 수 있다.

하지만 N이 매우 커졌을 때를 생각해보자.

N = 1,000,000

이라면

N² = 1,000,000,000,000
N  =         1,000,000

이다.

N²에 비하면 N이나 상수는 상대적으로 영향력이 매우 작아진다.

그래서 알고리즘의 성장률을 볼 때는 작은 차수를 제거하고 가장 빠르게 증가하는 항에 집중할 수 있다.

여기서 Tilde notation이 등장한다.

---

7. Tilde Notation ~

강의자료에서는 Tilde notation을 다음과 같이 설명한다.

lower-order terms를 무시하여 수학적 모델을 단순화한다.

예를 들어

f(N) = 1/2 N² + 3N + 7

이라면 N이 커질수록 가장 큰 영향을 주는 항은

1/2 N²

이다.

따라서

f(N) ~ 1/2 N²

처럼 표현할 수 있다.

여기서 중요한 점이 하나 있다.

Tilde notation에서는 최고차항의 계수까지 없애는 것이 아니다.

예를 들어

3N² + 10N + 5

라면

~ 3N²

이다.

~ N²이라고 하는 것과는 의미가 다르다.

왜냐하면 Tilde notation의 엄밀한 의미는

f(N) ~ g(N)

일 때

        f(N)
lim    ───── = 1
N→∞     g(N)

이기 때문이다.

예를 들어

f(N) = 3N² + 10N + 5
g(N) = 3N²

이면

3N² + 10N + 5
──────────────
     3N²

= 1 + 10/(3N) + 5/(3N²)

이고 N이 무한히 커지면

→ 1

이 된다.

따라서

3N² + 10N + 5 ~ 3N²

이다.

---

8. 그런데 Big-O에서는 계수도 무시한다

여기서 Tilde notation과 Big-O를 구분해야 한다.

예를 들어

f(N) = 3N² + 10N + 5

라고 하자.

Tilde notation에서는

f(N) ~ 3N²

이라고 한다.

반면 Big-O와 같은 점근적 표기에서는 보통

O(N²)

이라고 한다.

즉

Tilde
→ leading coefficient를 유지

Big-O 계열
→ 상수배까지 중요하지 않게 본다.

이 차이를 알아두면 둘을 혼동하지 않는다.

---

9. Big-O, Big-Ω, Big-Θ

알고리즘의 성장률을 표현할 때 자주 등장하는 세 가지 표기가 있다.

Big-O     O
Big-Omega Ω
Big-Theta Θ

가장 먼저 큰 그림을 잡으면

O(g(N))
→ 점근적 상한

Ω(g(N))
→ 점근적 하한

Θ(g(N))
→ 점근적으로 같은 차수

라고 이해할 수 있다.

그런데 여기서 상한과 하한이라는 표현을 정확히 이해해야 한다.

---

10. Big-O : 점근적 상한

어떤 알고리즘의 실행 횟수가

f(N) = 10N² + 3N + 20

이라고 하자.

Big-O는 충분히 큰 N에서

f(N) ≤ c · g(N)

을 만족하는 어떤 양의 상수 c와 기준점 N₀가 존재하는지를 본다.

예를 들어

g(N) = N²

라고 하자.

충분히 큰 N에서는

10N² + 3N + 20 ≤ 11N²

같은 관계를 만들 수 있다.

즉

f(N)
────────── 11N²

라는 위쪽 경계를 잡을 수 있다.

그래서

f(N) = O(N²)

라고 말할 수 있다.

핵심은 정확히 11이어야 한다는 것이 아니다.

20N²
100N²
1000N²

등 충분히 큰 상수배를 잡아도 된다.

Big-O는 어떤 상수배를 이용해서 위에서 덮을 수 있는가를 보는 것이다.

---

11. Big-Ω : 점근적 하한

같은 함수

f(N) = 10N² + 3N + 20

을 생각해보자.

이번에는 아래쪽 경계를 찾는다.

예를 들어

9N² ≤ 10N² + 3N + 20

은 충분히 큰 N에서 당연히 성립한다.

즉

9N²
────────── f(N)

처럼 아래에서 받칠 수 있다.

따라서

f(N) = Ω(N²)

라고 말할 수 있다.

Big-Ω의 핵심은

f(N) ≥ c · g(N)

이 되는 상수 c > 0과 충분히 큰 N이 존재한다는 것이다.

---

12. 내가 헷갈렸던 10N², 11N², 9N² 예제

처음에는 다음처럼 생각하기 쉽다.

10N² < 11N²
→ Big-O

10N² > 9N²
→ Big-Ω

직관 자체는 상한과 하한을 이해하는 데는 괜찮다.

       11N²       ← 위쪽 경계
        ↑
       10N²       ← 실제 함수
        ↑
        9N²       ← 아래쪽 경계

그래서

10N² = O(N²)

10N² = Ω(N²)

둘 다 맞다.

그리고 위와 아래에서 모두 같은 N² 차수로 잡을 수 있으므로

10N² = Θ(N²)

도 맞다.

다만 여기서 중요한 것은

11과 9라는 숫자 자체가 Big-O와 Big-Ω를 결정하는 것이 아니다.

Big-O와 Big-Ω에서는 상수배를 허용한다.

따라서 더 좋은 예제는 다음과 같다.

f(N) = 10N² + 3N + 20

충분히 큰 N에서

9N² ≤ f(N) ≤ 11N²

같은 형태의 경계를 잡을 수 있다면

f(N) = Ω(N²)
f(N) = O(N²)

이고 결과적으로

f(N) = Θ(N²)

이라고 볼 수 있다.

---

13. Big-O는 "정확한 실행시간"이 아니다

여기서 자주 하는 착각이 있다.

O(N²)

이라고 했다고 해서 실행 횟수가 정확히 N²번이라는 뜻은 아니다.

다음 함수들은 모두 O(N²)라고 할 수 있다.

N²
3N² + 10N
0.5N² + 100N + 300

상수배와 낮은 차수의 항을 무시하고 성장 속도의 상한을 보는 것이기 때문이다.

그리고 조금 더 엄밀하게 말하면

N

인 알고리즘도

O(N²)

라고 말할 수 있다.

왜냐하면 충분히 큰 N에서

N ≤ N²

이기 때문이다.

하지만 알고리즘의 성장률을 설명하면서 일부러 느슨하게

O(N²)

라고 표현하기보다는 더 정확한 경계인

O(N)

을 사용하는 것이 일반적으로 더 유용하다.

---

14. Big-Ω도 마찬가지다

Big-Ω는 하한이다.

예를 들어

f(N) = N²

이라면

f(N) = Ω(N²)

이다.

그런데

f(N) = Ω(N)

도 맞다.

왜냐하면 충분히 큰 N에서

N² ≥ N

이기 때문이다.

즉 Big-O와 Big-Ω는 각각 하나의 값만 가리키는 것이 아니라 가능한 상한과 하한의 집합을 표현한다고 생각하면 이해하기 쉽다.

---

15. Big-Θ는 위와 아래가 같은 경우

Big-Theta는 상한과 하한을 동시에 잡을 수 있을 때 사용한다.

c₁g(N) ≤ f(N) ≤ c₂g(N)

이 관계가 충분히 큰 N에서 성립한다면

f(N) = Θ(g(N))

이다.

예를 들어

f(N) = 10N² + 3N + 20

이라면 충분히 큰 N에서

c₁N² ≤ f(N) ≤ c₂N²

인 상수 c₁, c₂를 찾을 수 있다.

따라서

f(N) = Θ(N²)

이다.

그림으로 생각하면

c₂N²  ─────────────────  상한
              ↑
       f(N) = 10N² + 3N + 20
              ↓
c₁N²  ─────────────────  하한

처럼 f(N)을 같은 성장률을 가진 함수의 상수배 사이에 끼워 넣는 것이다.

---

16. O, Ω, Θ를 한 번에 이해하기

다음 함수가 있다고 하자.

f(N) = 5N² + 2N + 10

N이 충분히 커지면 N² 항이 지배한다.

그래서

f(N) = O(N²)

이라고 할 수 있다.

N²의 상수배가 위에서 f(N)을 덮을 수 있기 때문이다.

동시에

f(N) = Ω(N²)

이다.

N²의 상수배를 아래쪽 경계로 잡을 수 있기 때문이다.

두 조건이 모두 성립하므로

f(N) = Θ(N²)

이다.

정리하면

             위쪽 경계
                 ↓
Big-O      → 상한

Big-Theta  → 위와 아래가 같은 성장률

Big-Omega  → 하한
                 ↑
             아래쪽 경계

라고 기억할 수 있다.

---

17. Best Case와 Worst Case하고 같은 말일까?

여기서 또 하나 조심해야 한다.

흔히

Big-O = Worst Case
Big-Ω = Best Case

라고 외우기도 한다.

하지만 엄밀하게는 같은 개념이 아니다.

Big-O와 Big-Ω는 함수의 점근적 상한과 하한을 표현하는 수학적 표기법이다.

반면

Best Case
Worst Case
Average Case

는 어떤 입력 상황에서 비용을 분석하는지를 나타낸다.

예를 들어 Worst Case 실행시간 함수 자체에 대해서도

O(...)
Ω(...)
Θ(...)

를 이야기할 수 있다.

따라서 시험에서는 교수님 강의의 표현을 따라가되 개념적으로는

O  → asymptotic upper bound
Ω  → asymptotic lower bound
Θ  → asymptotically tight bound

로 이해해두는 것이 좋다.

---

18. Tilde와 Big-Theta는 비슷해 보이지만 다르다

다음 함수가 있다고 하자.

f(N) = 3N² + 10N + 5

Tilde notation에서는

f(N) ~ 3N²

이다.

왜냐하면

f(N) / 3N² → 1

이기 때문이다.

반면

f(N) = Θ(N²)

이다.

Theta에서는 상수배를 무시하기 때문이다.

그래서

Tilde
3N² + 10N + 5
        ↓
      ~ 3N²


Theta
3N² + 10N + 5
        ↓
      Θ(N²)

라고 구분하면 된다.

---

19. 1-SUM과 2-SUM으로 다시 돌아가보자

이제 처음의 알고리즘을 다시 보면 성장률이 보인다.

1-SUM

for (int i = 0; i < N; i++) {

    if (a[i] == 0) {
        count++;
    }
}

배열을 한 번 순회한다.

N에 비례

따라서 성장 차수는

Θ(N)

으로 이해할 수 있다.

2-SUM

for (int i = 0; i < N; i++) {

    for (int j = i + 1; j < N; j++) {

        if (a[i] + a[j] == 0) {
            count++;
        }
    }
}

두 원소의 모든 조합을 확인한다.

조합의 수는

N(N - 1) / 2

= 1/2 N² - 1/2 N

이다.

Tilde notation으로 보면

~ 1/2 N²

이고 성장 차수로 보면

Θ(N²)

이다.

즉 입력이 커질수록 1-SUM과 2-SUM의 차이는 급격히 커진다.

1-SUM → linear

2-SUM → quadratic

---

20. 자주 등장하는 성장률

알고리즘에서는 다음 성장률을 자주 보게 된다.

1
log N
N
N log N
N²
N³
2^N

입력 N이 커질수록 일반적으로

1
<
log N
<
N
<
N log N
<
N²
<
N³
<
2^N

순서로 빠르게 증가한다.

따라서 같은 문제를 해결한다면 보통 성장률이 낮은 알고리즘이 큰 입력에서 훨씬 유리하다.

---

핵심 정리

이번 내용을 공부하면서 가장 헷갈렸던 부분은 ~, O, Ω, Θ가 모두 비슷하게 보인다는 것이었다.

하지만 역할을 나누면 생각보다 간단하다.

Tilde ~

정확한 leading term에 관심
lower-order term 제거

3N² + 10N + 5
~ 3N²

Big-O

점근적 상한

f(N) ≤ c·g(N)

Big-Ω

점근적 하한

f(N) ≥ c·g(N)

Big-Θ

점근적으로 같은 성장 차수

c₁g(N) ≤ f(N) ≤ c₂g(N)

그리고

f(N) = 10N² + 3N + 20

같은 함수가 있다면 직관적으로

       c₂N²
         ↑
         │
       f(N)
         │
         ↓
       c₁N²

처럼 같은 N² 성장률의 함수 사이에 들어간다고 생각할 수 있다.

따라서

f(N) = O(N²)
f(N) = Ω(N²)
f(N) = Θ(N²)

이다.

결국 알고리즘 분석에서 궁금한 것은 작은 연산 몇 번의 차이가 아니다.

N이 매우 커졌을 때 무엇이 이 알고리즘의 실행 비용을 지배하는가?

이 질문을 답하기 위해 정확한 명령 횟수에서 출발해 Tilde notation으로 단순화하고, O·Ω·Θ 같은 점근적 표기법으로 성장률을 표현하는 것이다.