시간복잡도란? Big-O 표기법과 코드 분석으로 이해하기

반응형

 

시간복잡도란? Big-O 표기법과 코드 분석으로 이해하기

 

1. 시간복잡도란?

입력 크기 N이 커질수록 알고리즘이 얼마나 느려지는지를 예측하는 도구

 

시간복잡도는 입력 크기가 증가할 때 알고리즘의 실행 시간이 얼마나 빠르게 증가하는지를 나타내는 개념입니다.

여기서 중요한 점은 실제 실행 시간이 몇 초인지가 아니라, 입력 데이터의 크기 N이 커질수록 연산 횟수가 어떤 비율로 증가하는지를 보는 것입니다.

 

시간복잡도를 이해해야 하는 이유는 단순합니다.

작은 입력에서는 잘 동작하는 코드도 큰 입력에서는 전혀 사용할 수 없을 수 있기 때문입니다. 코딩 테스트나 실무 시스템에서는 데이터가 수천 개, 수백만 개 이상으로 커질 수 있습니다.

 

🔷 Big-O 복잡도 그래프

시간복잡도 그래프

 

 

2. Big-O 표기법 이해하기

시간복잡도를 표현할 때 가장 많이 사용하는 방식이 Big-O 표기법입니다.

Big-O 표기법은 알고리즘의 실행 시간이 입력 크기 N에 따라 얼마나 증가하는지를 간단하게 나타냅니다.

 

✔️ 가장 대표적인 시간복잡도는 다음과 같습니다.

표기법	의미	예시
O(1)	입력 크기와 관계없이 일정한 시간	배열 인덱스 접근
O(log N)	입력이 커져도 실행 횟수가 천천히 증가	이진 탐색
O(N)	입력 크기에 비례해서 증가	단일 반복문
O(N log N)	효율적인 정렬 알고리즘에서 자주 등장	병합 정렬, 퀵 정렬 평균
O(N²)	입력 크기의 제곱만큼 증가	중첩 반복문

 

✔️ 예를 들어 배열에서 특정 인덱스의 값을 가져오는 작업은 입력 크기와 관계없이 한 번에 접근할 수 있습니다.

int value = arr[3];

이 경우 배열의 크기가 10개든 100만 개든 특정 위치에 접근하는 시간은 거의 일정합니다. 따라서 시간복잡도는 O(1)입니다.

 

✔️ 반면, 배열에서 특정 값을 찾기 위해 처음부터 끝까지 확인해야 한다면 입력 크기만큼 반복해야 합니다.

for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        return i;
    }
}

이 경우 최악의 상황에서는 배열의 모든 요소를 확인해야 하므로 시간복잡도는 O(N)입니다.

 

✔️ 또한 반복문 안에 반복문이 있는 경우에는 실행 횟수가 크게 증가합니다.

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

위 코드는 바깥 반복문이 n번 실행되고, 그때마다 안쪽 반복문도 n번 실행됩니다. 따라서 총 실행 횟수는 n × n이 되어 시간복잡도는 O(N²)입니다.

반응형

 

3. 코드 예제로 이해하는 시간복잡도 분석

시간복잡도를 가장 잘 이해하는 방법은 실제 코드를 보면서 분석해 보는 것입니다.

코드에서 반복문이 몇 번 실행되는지, 반복문이 서로 중첩되어 있는지, 또는 반복이 진행될수록 입력 크기가 줄어드는 구조인지에 따라 시간복잡도는 달라집니다.

 

✔️ 한 번만 실행되는 코드: O(1)

int a = 10;
int b = 20;
int sum = a + b;
System.out.println(sum);
int value = arr[3];

위 코드는 입력 크기와 관계없이 정해진 횟수만 실행됩니다.

 

데이터가 10개이든 10만 개이든 실행 횟수는 거의 변하지 않습니다.
따라서 시간복잡도는 O(1)입니다.

 

이처럼 입력 크기와 무관하게 일정한 시간이 걸리는 코드를 상수 시간이라고 합니다.

 

✔️ 단일 반복문: O(N)

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

위 코드는 i가 0부터 n - 1까지 증가하므로 총 n번 실행됩니다.

즉, 입력 크기 n이 10이면 10번, 1,000이면 1,000번 실행됩니다.
따라서 시간복잡도는 O(N)입니다.

배열 전체를 순회하면서 합계를 구하는 코드도 같은 방식으로 분석할 수 있습니다.

int sum = 0;

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

배열의 모든 요소를 한 번씩 확인하므로 배열의 길이를 N이라고 할 때 시간복잡도는 O(N)입니다.

 

✔️ 조건문이 포함된 반복문: O(N)

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

위 코드에는 반복문 안에 조건문이 들어 있습니다.

 

하지만 조건문이 포함되어 있다고 해서 시간복잡도가 크게 달라지는 것은 아닙니다.
반복문은 여전히 n번 실행되고, 각 반복에서 짝수인지 확인하는 연산은 상수 시간에 처리됩니다.

 

따라서 전체 시간복잡도는 O(N)입니다.

 

즉, 반복문 내부에 간단한 조건문이나 계산식이 들어가더라도, 전체 반복 횟수가 N번이라면 보통 O(N)으로 분석합니다.

 

✔️ 두 개의 반복문이 나란히 있는 경우: O(N)

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

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

첫 번째 반복문은 n번 실행되고, 두 번째 반복문도 n번 실행됩니다.

 

따라서 전체 실행 횟수는 다음과 같습니다.

n + n = 2N

처음에는 시간복잡도가 O(2N)처럼 보일 수 있습니다.
하지만 Big-O 표기법에서는 상수 계수를 제거합니다.

 

따라서 시간복잡도는 O(N)입니다.

 

반복문이 세 개여도 마찬가지입니다.

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

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

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

각 반복문이 독립적으로 n번씩 실행되므로 전체 실행 횟수는 3N입니다.
하지만 Big-O 표기법에서는 상수 계수를 제외하므로 이 경우에도 시간복잡도는 O(N)입니다.

 

✔️ 서로 다른 입력 크기를 사용하는 반복문: O(N + M)

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

for (int j = 0; j < m; j++) {
    System.out.println(j);
}

첫 번째 반복문은 n번 실행되고, 두 번째 반복문은 m번 실행됩니다.

 

이때 n과 m은 서로 다른 입력 크기입니다.
따라서 전체 시간복잡도는 O(N + M)으로 표현합니다.

 

만약 n과 m이 항상 비슷한 규모라고 가정할 수 있다면 O(N)처럼 단순화해서 볼 수도 있습니다.
하지만 두 입력 크기가 서로 독립적이라면 O(N + M)으로 표현하는 것이 더 정확합니다.

 

✔️ 중첩 반복문: O(N²)

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

바깥 반복문은 n번 실행됩니다.
그리고 바깥 반복문이 한 번 실행될 때마다 안쪽 반복문도 n번 실행됩니다.

따라서 전체 실행 횟수는 다음과 같습니다

n × n = n²

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

중첩 반복문은 입력 크기가 커질수록 실행 횟수가 매우 빠르게 증가합니다.
예를 들어 n = 1,000이면 약 1,000,000번의 반복이 발생합니다.

 

그래서 중첩 반복문을 사용할 때는 입력 크기가 커졌을 때 실행 시간이 얼마나 늘어나는지 반드시 고려해야 합니다.

 

✔️ 삼중 반복문: O(N³)

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

이 코드는 반복문이 세 단계로 중첩되어 있습니다.

각 반복문이 모두 n번씩 실행되므로 전체 실행 횟수는 다음과 같습니다.

n × n × n = n³

따라서 시간복잡도는 O(N³)입니다.

이런 구조는 입력 크기가 조금만 커져도 실행 시간이 크게 증가합니다.
따라서 실무나 코딩 테스트에서는 꼭 필요한 경우가 아니라면 피하는 것이 좋습니다.

 

✔️ 안쪽 반복문의 범위가 바깥 변수에 따라 달라지는 경우: O(N²)

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

이 코드는 안쪽 반복문이 항상 n번 실행되지는 않습니다.
i = 0일 때는 0번,
i = 1일 때는 1번,
i = 2일 때는 2번,
마지막에는 n - 1번 실행됩니다.

 

전체 실행 횟수는 다음과 같습니다.

0 + 1 + 2 + ... + (n - 1)

이 합은 대략 다음과 같습니다.

n(n - 1) / 2

Big-O 표기법에서는 상수와 낮은 차수를 제거하므로 최종 시간복잡도는 O(N²)입니다.

중요한 점은 정확한 실행 횟수가 n² / 2에 가깝더라도, 증가율 기준으로는 O(N²)으로 본다는 것입니다.

 

✔️ 반복 횟수가 절반씩 줄어드는 경우: O(log N)

while (n > 1) {
    n = n / 2;
}

위 코드는 반복이 한 번 실행될 때마다 n이 절반으로 줄어듭니다.

 

예를 들어 n = 16이라면 다음과 같이 변합니다.

16 → 8 → 4 → 2 → 1

총 4번 정도 반복됩니다.
n = 1,024라면 약 10번 반복됩니다.

 

즉, 입력 크기가 커지더라도 반복 횟수는 매우 천천히 증가합니다.
이처럼 입력 크기가 절반씩 줄어드는 구조의 시간복잡도는 보통 O(log N)입니다.

 

✔️ 반복문 안에서 절반씩 줄어드는 작업: O(N log N)

for (int i = 0; i < n; i++) {
    int temp = n;

    while (temp > 1) {
        temp = temp / 2;
    }
}

이 코드는 바깥 반복문과 안쪽 while문을 함께 봐야 합니다.

바깥 반복문은 n번 실행됩니다.
그리고 안쪽 while문은 매번 log N번 정도 실행됩니다.

 

따라서 전체 시간복잡도는 다음과 같습니다.

N × log N

즉, 시간복잡도는 O(N log N)입니다.

이 복잡도는 효율적인 정렬 알고리즘에서 자주 등장합니다.
대표적으로 병합 정렬과 힙 정렬이 있습니다.

 

✔️ 배열에서 특정 값을 찾는 경우: O(N)

int findIndex(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }

    return -1;
}

이 코드는 배열의 앞에서부터 값을 하나씩 확인합니다.

 

운이 좋으면 첫 번째 요소에서 바로 값을 찾을 수 있습니다.
이 경우는 최선의 경우이며, 시간복잡도는 O(1)입니다.

 

하지만 찾는 값이 배열의 마지막에 있거나, 아예 배열 안에 없다면 모든 요소를 확인해야 합니다.
이 경우는 최악의 경우이며, 시간복잡도는 O(N)입니다.

 

일반적으로 시간복잡도를 말할 때는 최악의 경우를 기준으로 설명하는 경우가 많습니다.
따라서 이 코드는 보통 O(N)으로 분석합니다.

 

✔️ HashMap을 사용한 조회: 평균 O(1)

Map<String, Integer> map = new HashMap<>();

map.put("apple", 100);
map.put("banana", 200);

int price = map.get("apple");

HashMap은 키를 이용해서 값을 빠르게 조회할 수 있는 자료구조입니다.

 

일반적으로 HashMap의 삽입, 조회, 삭제 연산은 평균적으로 O(1)에 가깝습니다.

 

배열이나 리스트에서 특정 값을 찾으려면 앞에서부터 하나씩 비교해야 하므로 O(N)이 걸릴 수 있습니다.
하지만 HashMap은 키를 기준으로 값을 바로 찾을 수 있기 때문에 훨씬 효율적으로 동작합니다.

 

✔️ 리스트에서 삭제할 때의 시간복잡도

자료구조에 따라 같은 작업이라도 시간복잡도가 달라질 수 있습니다.

List<Integer> list = new ArrayList<>();

list.add(10);
list.add(20);
list.add(30);

list.remove(0);

ArrayList에서 맨 앞 요소를 삭제하면 뒤에 있는 요소들을 앞으로 한 칸씩 이동해야 합니다.
따라서 삭제 위치에 따라 시간복잡도는 O(N)이 될 수 있습니다.

 

반면 마지막 요소를 삭제하는 경우는 상대적으로 빠릅니다.

list.remove(list.size() - 1);

마지막 요소는 뒤에 이동시킬 요소가 없으므로 보통 O(1)에 가깝습니다.
이처럼 같은 삭제 연산이라도 위치와 자료구조에 따라 성능이 달라집니다.

 

4. 시간복잡도 개선 사례

시간복잡도는 단순히 코드를 분석하기 위한 개념이 아닙니다.
더 효율적인 알고리즘이나 자료구조를 선택하기 위한 기준이기도 합니다.

 

✔️ 배열 검색: O(N)에서 O(1)로 개선하기

먼저 배열에서 특정 값이 있는지 확인하는 코드입니다.

boolean containsValue(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) {
            return true;
        }
    }

    return false;
}

이 코드는 배열을 처음부터 끝까지 순회하면서 target이 있는지 확인합니다.
최악의 경우 배열의 모든 요소를 확인해야 하므로 시간복잡도는 O(N)입니다.

이 작업이 한 번만 필요하다면 큰 문제가 없을 수 있습니다.
하지만 같은 배열에서 여러 번 값을 찾아야 한다면 매번 O(N)이 소요되어 비효율적입니다.

이 경우 HashSet을 사용하면 조회 성능을 개선할 수 있습니다.

Set<Integer> set = new HashSet<>();

for (int num : arr) {
    set.add(num);
}

boolean result = set.contains(target);

HashSet에 값을 미리 저장해 두면 contains 연산은 평균적으로 O(1)입니다.
따라서 여러 번 조회해야 하는 상황에서는 배열을 매번 순회하는 것보다 훨씬 효율적입니다.

 

단, HashSet을 만드는 데는 한 번 O(N)의 시간이 필요합니다. 따라서 조회가 여러 번 반복되는 상황에서 특히 효과적인 개선 방법입니다.

 

✔️ 두 수의 합 찾기: O(N²)에서 O(N)으로 개선하기

먼저 모든 숫자 쌍을 비교하는 방식입니다.

boolean hasTwoSum(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == target) {
                return true;
            }
        }
    }
    return false;
}

이 코드는 모든 숫자 쌍을 하나씩 확인합니다.
바깥 반복문과 안쪽 반복문이 중첩되어 있으므로 최악의 경우 시간복잡도는 O(N²)입니다.

HashSet을 사용하면 한 번의 순회로 개선할 수 있습니다.

boolean hasTwoSum(int[] arr, int target) {
    Set<Integer> set = new HashSet<>();
    for (int num : arr) {
        int needed = target - num;
        if (set.contains(needed)) {
            return true;
        }
        set.add(num);
    }
    return false;
}

현재 숫자 num에 대해 필요한 값은 target - num입니다.
이미 그 값이 HashSet에 존재한다면 두 수의 합으로 target을 만들 수 있습니다.

배열을 한 번만 순회하고, HashSet의 조회와 삽입은 평균적으로 O(1)이므로 전체 시간복잡도는 O(N)입니다.

 

✔️ 문자열 누적: O(N²)에서 O(N)으로 개선

먼저 비효율적인 문자열 누적 방식입니다.

String result = "";

for (int i = 0; i < n; i++) {
    result += i;
}

Java의 String은 불변 객체입니다.
따라서 문자열을 더할 때마다 새로운 문자열이 생성됩니다.

반복이 진행될수록 기존 문자열을 복사하는 비용이 커지기 때문에 전체 시간복잡도는 O(N²)에 가까워질 수 있습니다.

이 경우 StringBuilder를 사용하는 것이 좋습니다.

StringBuilder sb = new StringBuilder();

for (int i = 0; i < n; i++) {
    sb.append(i);
}

String result = sb.toString();

StringBuilder는 내부 버퍼를 사용하여 문자열을 효율적으로 추가합니다.
따라서 반복문 안에서 문자열을 누적해야 할 때는 String 덧셈보다 훨씬 적합합니다.

전체 시간복잡도는 일반적으로 O(N)에 가깝게 개선됩니다.

 

✔️ 리스트 반복 검색: O(N)에서 O(1) 조회로 개선하기

먼저 List에서 특정 값이 존재하는지 확인하는 코드입니다.

boolean exists(List<String> names, String target) {
    for (String name : names) {
        if (name.equals(target)) {
            return true;
        }
    }

    return false;
}

List에서 특정 값이 존재하는지 확인하려면 앞에서부터 하나씩 비교해야 합니다.
따라서 한 번의 검색은 최악의 경우 O(N)입니다.

검색이 한 번이라면 괜찮을 수 있지만, 같은 목록에서 여러 번 검색한다면 성능이 나빠질 수 있습니다.

이 경우 HashSet으로 변환해 두면 검색 비용을 줄일 수 있습니다.

Set<String> nameSet = new HashSet<>(names);

boolean result = nameSet.contains(target);

HashSet의 contains 연산은 평균적으로 O(1)입니다.
처음 HashSet을 만드는 데 O(N)이 필요하지만, 이후 여러 번 검색할 때는 훨씬 효율적입니다.

즉, 반복 조회가 많은 상황에서는 List보다 HashSet이 더 적합할 수 있습니다.

---

※ 게시된 글 및 이미지 중 일부는 AI 도구의 도움을 받아 생성되거나 다듬어졌습니다.

반응형