시간복잡도, 내가 이해한 만큼 풀어쓴 이야기

문제 상황

내가 개발을 시작하고 어느 정도 코드를 짜기 시작했을 때, 종종 이런 말을 들었다.
“그 코드의 시간복잡도는 어떻게 돼?”
솔직히 말하면, 처음에는 이 말이 너무 어렵게 느껴졌다.
시간복잡도가 뭔데? 그냥 코드가 빠르면 빠른 거고 느리면 느린 거 아닌가?

그러다가 어느 순간부터, “왜 내 프로그램은 데이터가 많아지면 급격하게 느려질까?” 하는 의문이 들었다.
그때부터 조금씩 시간복잡도의 필요성을 깨닫게 됐다.
시간복잡도는 프로그램이 처리해야 하는 데이터의 양이 커질수록, 걸리는 시간이 얼마나 늘어나는지를 설명해주는 개념이다.

예를 들어, 내가 좋아하는 마트에 줄을 선다고 해보자.
줄이 2명일 땐 금방 계산대에 간다.
근데 줄이 200명이 되면?
줄이 길어질수록 대기 시간도 비례해서 늘어나게 된다.
이 늘어나는 속도를 수학적으로 표현한 게 바로 시간복잡도다.

내가 시도한 방법

시간복잡도를 처음 이해하려 할 때, 책에 나오는 수식부터 파고들었다.
O(1), O(n), O(n²)...
솔직히 처음엔 이 기호들이 마치 암호처럼 보였다.
그래서 나는 이런 기호를 단순히 속도로만 바꿔보며 이해하려 했다.

예를 들어:

• O(1): 입력 데이터의 크기에 상관없이 항상 같은 시간. 즉, “초단위 고정 속도” 계산.
• O(n): 데이터가 늘어나면, 처리 시간도 그만큼 같이 늘어남.
• O(n²): 데이터가 조금 늘어도 시간이 기하급수적으로 늘어남.

이렇게 간단한 예시로 먼저 익숙해지고, 실제 코드에 대입해 보려고 했다.

해결 과정 및 코드 예시

이제 좀 더 구체적으로 살펴보자.
아래에 간단한 예시 코드를 적어본다.

// O(1) 예제: 항상 같은 횟수만 실행
public int getFirstElement(int[] arr) {
    return arr[0];
}

**O(1)**은 입력 배열 크기가 커져도 arr[0]을 꺼내는 데 걸리는 시간은 변하지 않는다.
마치 마트 계산대에서 “제일 앞에 있는 사람”만 처리하는 것과 같다.

// O(n) 예제: 배열을 모두 순회
public int sum(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

**O(n)**은 데이터가 10개면 10번, 100개면 100번 반복한다.
줄에 서 있는 모든 사람의 이름을 한 명씩 부르는 것과 같다.

// O(n^2) 예제: 이중 반복문
public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

**O(n²)**는 데이터가 10개면 100번, 100개면 10,000번 실행된다.
모든 사람이 서로 인사를 주고받는다고 상상해보자.
사람 수가 조금만 늘어나도 시간이 폭발적으로 늘어난다.

이렇게 실제 코드에 대입해보면 복잡도가 몸으로 와닿는다.

전문 용어도 조금

시간복잡도를 얘기할 때 “빅오 표기법(Big O Notation)”이라는 용어를 쓴다.
이는 최악의 경우(worst case)를 기준으로 시간 증가량을 표현한다.
아래는 대표적인 표기법과 의미다.

• O(1): 상수 시간(Constant Time)
• O(log n): 로그 시간(Logarithmic Time)
  • 예: 이진 탐색
• O(n): 선형 시간(Linear Time)
• O(n log n): 로그 선형 시간
  • 예: 효율적인 정렬 알고리즘(퀵 정렬 평균)
• O(n²): 이차 시간(Quadratic Time)

이 외에도 O(2^n), O(n!) 같은 더 복잡한 것도 있다.
하지만 일단 위 정도만 알아도 대부분의 코드에서 충분히 활용할 수 있다.

정리 및 느낀 점

시간복잡도는 결국 이렇게 요약된다.

데이터가 늘어날수록 프로그램이 얼마나 느려지는지 예측하고, 더 나은 방법을 찾기 위해 쓰는 도구.

처음에는 어렵게 느껴졌지만,
“줄 서기” “모두가 인사하기” 같은 일상적인 비유를 떠올리면 훨씬 이해가 쉽다.
나는 아직도 코드를 짤 때 이 복잡도를 완벽히 계산하진 못하지만,
“이 반복문이 늘어나면 얼마나 느려질까?” 하고 의문을 갖는 것만으로도 코드 품질이 달라진다고 느낀다.

혹시 나처럼 시간복잡도가 어려운 분들이 있다면,
한 번쯤 직접 손으로 반복문을 세어보길 추천한다.
그리고 작은 배열부터 큰 배열로 테스트해보면,
어떤 코드가 폭발적으로 느려지는지 체감할 수 있다.