[IT Info] 시간복잡도 O(n) vs O(n^2): 데이터 크기가 달라지면 알고리즘의 성능은 어떻게 될까?

1. 시간복잡도 O(n) vs O(n^2) : 데이터 크기가 달라지면 알고리즘의 성능은 어떻게 될까?

코딩을 하다 보면 "시간 복잡도"라는 말을 자주 듣게 됩니다. 특히 O(n)과 O(n^2)는 가장 흔하게 접하는 개념이죠. 이 두 가지가 정확히 무엇을 의미하고, 왜 중요한지 간단히 알아볼까요?

시간 복잡도, 왜 알아야 할까?

시간 복잡도는 알고리즘의 성능을 평가하는 척도입니다. "입력 데이터의 크기(n)"가 커짐에 따라 알고리즘의 "실행 시간"이 얼마나 늘어나는지 수학적으로 표현한 것입니다. 간단히 말해, 데이터가 많아질 때 내 코드가 얼마나 빠르게 혹은 느리게 작동하는지 예측하는 데 도움을 줍니다.

 

2. O(n): 선형 시간 복잡도

O(n)은 "선형 시간 복잡도"라고 부릅니다.

• 특징: 입력 크기 n이 커지는 만큼 실행 시간도 정확히 비례해서 증가합니다.
• 예시: 데이터가 100개일 때 1초가 걸렸다면, 데이터가 200개일 때는 약 2초, 1,000개일 때는 약 10초가 걸립니다. 데이터의 수가 2배가 되면, 실행 시간도 2배가 되는 식이죠.
• 대표적인 코드: 배열에서 특정 값을 찾는 단순한 반복문이 이에 해당합니다.

python

# O(n) 예제 코드
for i in range(n):
    # 이 코드는 n번 실행됩니다.
    print(i)

 

3. O(n^2): 이차 시간 복잡도

O(n^2)는 "이차 시간 복잡도"라고 부릅니다.

• 특징: 입력 크기 n이 커질수록 실행 시간은 n의 제곱에 비례하여 증가합니다.
• 예시: 데이터가 100개일 때 1초가 걸렸다면, 데이터가 200개일 때는 약 2^2=4배인 4초, 1,000개일 때는 10^2=100배인 100초가 걸립니다. 데이터가 2배가 되면 실행 시간은 4배가 됩니다.
• 대표적인 코드: 배열의 모든 요소를 서로 비교해야 하는 중첩된 반복문이 대표적입니다. (예: 버블 정렬)

python

# O(n^2) 예제 코드
for i in range(n):
    for j in range(n):
        # 이 코드는 n * n번 실행됩니다.
        print(i, j)

 

4. O(n) vs O(n^2), 무엇이 더 좋을까?

두 알고리즘의 성능 차이는 n이 커질수록 극명하게 드러납니다.

 

                                       O(n)                                                                         O(n^2)

속도	데이터가 많아져도 비교적 안정적입니다.	데이터가 많아질수록 매우 느려집니다.
성장률	선형적으로 증가	제곱에 비례하여 기하급수적으로 증가
일반적인 형태	단일 반복문	중첩된 반복문
예시 (n=10,000)	약 1만 번의 연산	약 1억 번의 연산

위 표에서 볼 수 있듯이, 데이터의 양이 적을 때는 별 차이가 없어 보이지만, 데이터가 1만 개만 되어도 O(n^2)는 O(n)에 비해 1만 배나 느립니다. 이 차이는 데이터가 많아질수록 더욱 커집니다.

 

5. 현업 개발자에게 중요한 이유

웹 서비스나 애플리케이션을 개발할 때, 수십만, 수백만 개의 데이터를 처리하는 일은 흔합니다. 이때 O(n^2) 같은 비효율적인 알고리즘을 사용하면 서비스 전체가 느려지거나 멈춰버릴 수 있습니다. 효율적인 O(n) 알고리즘을 선택하는 것은 사용자 경험을 향상시키고 시스템 안정성을 보장하는 데 매우 중요합니다.

알고리즘의 시간 복잡도를 이해하는 것은 단순히 지식을 아는 것을 넘어, 더 빠르고 효율적인 코드를 작성하는 개발자의 필수 역량입니다.