시간 복잡도 계산하는 방법

시간 복잡도 계산하는 방법

좋은 알고리즘이란 같은 문제를 더 빠르고 효율적으로 해결하는 코드를 말합니다.
같은 기능을 수행하더라도 어떤 코드는 5초가 걸리고, 어떤 코드는 0.1초 만에 끝나기도 하죠.

 

그렇다면 우리는 좋은 알고리즘을 어떻게 판단할 수 있을까요? 🤔

 

실행 속도나 메모리 사용량을 직접 수치로 측정할 수도 있지만,
컴퓨터의 성능, 운영체제, 입력값 등에 따라 실제 실행 시간은 매번 달라집니다.

 

그래서 우리는 실행 시간을 직접 측정하는 대신,
코드의 구조를 바탕으로 예측하는 방법을 사용합니다.
이것이 바로 시간 복잡도(Time Complexity)입니다.

 

시간 복잡도란?

---

시간 복잡도

시간 복잡도(Time Complexity)란,
입력 크기 N이 커질수록 알고리즘의 실행 시간이 얼마나 증가하는지를 수학적으로 표현한 것입니다.

 

즉, "데이터가 많아질수록 실행 시간이 얼마나 늘어나는가?"를 나타내는 지표입니다.

 

시간 복잡도는 절대적인 "초 단위의 실행 시간"이 아니라, 입력 크기에 따른 상대적인 성능 변화를 의미합니다.

예시로 살펴보기

문제:
정수 배열에서 음수가 있다면 그 값을 반환하라.
(음수가 여러 개라면 첫 번째 음수를 반환한다.)

public int solution(int[] array) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] < 0) return array[i];
    }
    return 0;
}

이 알고리즘의 실행 횟수(반복 횟수)는 배열의 구성에 따라 달라집니다.

 

입력 배열	탐색 횟수	설명
{-5, 2, 3, 7, 10}	1회	첫 번째 요소가 음수이므로 즉시 종료
{2, 3, -5, 7, 10}	3회	세 번째 요소에서 음수를 발견
{2, 3, 7, 10, -5}	5회	끝까지 탐색 후 마지막에서 음수를 발견

즉, 같은 코드라도 입력값에 따라 실행 속도가 달라질 수 있습니다.
이처럼 알고리즘의 효율성을 판단하기 위해
입력 크기와 실행 시간의 관계를 수학적으로 표현한 것이 바로 시간 복잡도입니다.

 

시간 복잡도 표기법 ― Big-O, Big-Ω, Big-Θ

---

앞서 본 것처럼, 알고리즘은 입력 데이터의 구성에 따라 실행 시간이 달라질 수 있습니다.
이런 다양한 상황을 구분하기 위해 시간 복잡도는 세 가지 관점으로 표현합니다.

 

표기법	의미	설명
Big-Ω (오메가)	최선의 경우	알고리즘이 가장 빠르게 끝나는 상황
Big-Θ (세타)	평균적인 경우	일반적인 입력에 대한 평균 성능
Big-O (빅오)	최악의 경우	입력이 가장 불리할 때 걸리는 시간

일반적으로는 최악의 경우(Big-O)를 기준으로 알고리즘의 성능을 평가합니다.
그 이유는 프로그램이 항상 최악의 상황에서도 안정적으로 동작해야 하기 때문입니다.

 

앞서 본 예제에서 최악의 경우는
배열의 마지막 요소까지 탐색해야 하는 경우입니다.

 

배열의 길이가 N이라면, 반복문은 N번 수행되므로

 

시간 복잡도 = O(N)

이 됩니다.

 

시간 복잡도를 단순화하는 법칙

---

시간 복잡도를 계산할 때는 가장 영향이 큰 항만 남기고 나머지는 생략합니다.
즉, 세부적인 상수나 작은 항보다는 성능에 결정적인 영향을 미치는 요소에 집중하는 것이 핵심입니다.

• 반복문이 N - 1번 돌아도 → O(N)
• 반복문이 N² + 10N + 5번 돌아도 → O(N²)

결국, 성능에 가장 큰 영향을 미치는 항만 남긴다는 것이 핵심 원칙입니다.

public int solution(int[] array) {
    if (array[0] < 0) return array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < 0) return array[i];
    }
    return 0;
}

 

이 코드는 반복 횟수를 N - 1로 줄였지만,
실제로는 여전히 모든 데이터를 한 번씩 검사할 수 있으므로

 

시간 복잡도는 O(N) 으로 동일하게 평가됩니다.

 

대표적인 시간 복잡도 종류

---

시간 복잡도는 알고리즘이 입력 크기(N)에 따라 얼마나 빨리 또는 느리게 동작하는지를 표현합니다.
아래 표는 대표적인 시간 복잡도와 그 특징을 정리한 것입니다.

 

표기	이름	예시 코드	특징
O(1)	상수 시간(Constant Time)	배열 인덱스 접근	입력 크기와 관계없이 일정한 시간
O(log N)	로그 시간(Logarithmic Time)	이진 탐색(Binary Search)	입력이 커질수록 느리게 증가
O(N)	선형 시간(Linear Time)	단순 반복문	데이터 크기에 비례하여 증가
O(N log N)	로그 선형(Log-linear Time)	정렬 알고리즘(퀵 정렬, 병합 정렬 등)	실무에서 효율적인 정렬 성능
O(N²)	제곱 시간(Quadratic Time)	중첩 반복문	데이터가 많아질수록 급격히 느려짐
O(2ⁿ)	지수 시간(Expotnential Time)	재귀적 조합 탐색	입력이 조금만 커져도 매우 느려짐

 

아래 그래프는 시간 복잡도에 따른 실행 속도 차이를 시각적으로 표현한 것입니다.

 

출처: www.freecodecamp.org

데이터의 양이 커질수록 시간 복잡도 간의 성능 차이는 기하급수적으로 커집니다.

예를 들어, O(N)과 O(N²) 알고리즘은
입력 크기가 작을 때는 비슷해 보이지만,
데이터가 커질수록 수십 배, 수백 배 이상의 차이가 나타납니다.

 

빠른 알고리즘을 설계한다는 것은 곧 더 낮은 차수의 시간 복잡도를 가진 코드를 만드는 것을 의미합니다.

 

좋은 알고리즘이란 단순히 빨리 끝나는 코드가 아니라,
입력 데이터가 커져도 안정적인 성능을 유지하는 코드입니다.

 

시간 복잡도는 코드의 효율성을 예측하는 수학적 도구
좋은 알고리즘이란 더 낮은 차수의 시간 복잡도를 가지는 코드

즉, 좋은 알고리즘을 설계한다는 것은
변화하는 입력 크기에도 꾸준히 효율적인 코드를 만드는 일입니다.

 

앞으로는 이런 효율적인 동작을 신경쓰며 코드를 작성해보도록 노력해봐야겠어요!