[Java] 시간복잡도와 빅 오(Big-O) 표기의 이해

알고리즘(Algorithm)이란?

알고리즘이란 어떠한 문제를 해결하기 위한 단계적인 절차 또는 방법입니다. 저희는 단순히 문제를 해결하는 것만이 아닌, 더 빠르고 더 효율적인 방법을 고민해야 합니다. 그래서 알고리즘을 평가할 때 보통 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)를 고려해야 합니다.

 

 

즉 좋은 알고리즘이란 메모리를 적게 사용하고, 빠르게 실행되는것이며, 알고리즘의 효율성은 시간복잡도와 공간복잡도를 기준으로 판단합니다. 

 

그렇다면 먼저 알고리즘이 얼마나 빠르게 실행되는지를 나타내는 시간복잡도(Time Complexity)에 대해 알아보겠습니다.

 

 

시간복잡도(Time Complexity)란?

시간복잡도는 입력 데이터의 크기(n)가 증가할 때, 알고리즘의 실행 시간이 얼마나 증가하는지를 나타내는 개념입니다. 여기서 중요한 점은 정확한 실행 시간이 아니라, 데이터의 크기가 커질수록 연산 횟수가 어떻게 증가하는지를 분석합니다.

 

즉 데이터의 크기와 알고리즘 수행 시간이 어떤 증가 패턴을 보이는지를 나타내는 성능 지표입니다.

쉽게 말하자면 데이터의 크기가 2배가 증가한다면 알고리즘의 수행 시간도 비례해서 2배가 증가 하는지, 아니면 4배, 10배 그 이상 증가하는지 이러한 증가 경향(성장 속도)를 분석합니다.

 

여기서 실행 시간이 아닌 증가 패턴을 분석하는 이유는, 실행 시간은 CPU 성능과 메모리, JVM 등에 따라 달라지지만 알고리즘(증가 패턴)은 변하지 않습니다. 그래서 저희는 증가 패턴을 기준으로 알고리즘을 비교합니다.

 

 

시간복잡도가 필요한 이유

작은 데이터에서는 대부분의 알고리즘이 빠르게 실행됩니다. 하지만 데이터가 많아질수록 알고리즘에 따라 실행 시간의 차이가 크게 벌어지기에, 저희들은 항상 데이터가 커졌을때도 감당 가능한 알고리즘인지를 고민해야 합니다. 이를 비교하기 위한 기준이 바로 시간 복잡도입니다.

빅 오 (Big - O)란?

Big-O 표기법은 시간복잡도를 표현하는 대표적인 방법입니다. Big-O는 데이터의 크기(n)가 증가할 때 알고리즘의 실행 시간이 어떤 증가 패턴을 보이는지를 나타내는 표기법입니다. 앞서 말한것처럼 정확한 실행 시간이 아닌 입력이 커질수록 실행 시간이 어떤 속도로 증가하는지를 분석합니다.

 

Big-O는 보통 최악의 경우를 기준으로 설명하며, 그 이유는 프로그램이 최악의 상황에서도 항상 안정적으로 동작해야 하기 때문입니다.  

시간 복잡도	증가 속도	설명
O(1)  상수	입력 크기와 상관 없이 일정함	배열에서 한 개의 데이터를 찾을 때
O(n) 선형	입력 크기와 비례하여 증가	선형 탐색 알고리즘 (배열에서 특정 값 비교)
O(n2) 제곱	입력 크기와 비례하여 제곱 증가	이중 반복문
O(log n) 로그	입력 크기 증가함에 따라 실행 시간이 로그 함수의 형태로 증가(매우 느리게 증가)	이진 탐색 알고리즘 (배열의 중앙 값 찾기)
O(n log n) 로그 선형	입력 크기의 증가함에 따라 실행 시간이 로그 함수와 선형 함수의 곱의 형태로 증가 : O(log n) * O(n) (선형보다 조금 빠르게 증가)	병합 정렬 (데이터의 개수를 로그 단계동안 반복)

 

Big-O 표기

보통 Big-O는 표기할 때 상수와 낮은 차수를 무시합니다. 

예를 들어 O(2n + 100)의 식이 있다고 하면, 이를 Big-O로 표현하면 O(n)과 같이 단순화 됩니다.

기본식 : O(2n + 100)
       ↓
Big-O  : O(n)

그 이유는 데이터의 크기가 커질수록 상수(2, 100)의 영향은 거의 없어지기 때문입니다.

데이터의 크기(n)를 1,000,000이라고 가정 하겠습니다.

n = 1,000,000
2n + 100 = 2,000,100

 

여기서 +100은 큰 의미가 없으며, 2배라는 상수 배율 역시 전체 증가 흐름을 바꾸지는 않습니다.

Big-O에서 중요한 것은 입력이 커질수록 얼마나 빠르게 증가하는가 입니다.

 

그러면 여기서 의문이 들 수 있습니다.

2배가 왜 증가 흐름을 바꾸지 않는지, 얼마나 빠르게 증가하느냐가 무슨 의미인지?

 

이 의문을 직관적으로 이해하기 위해 간단한 예시를 들어보겠습니다.

n = 1,000
O(n) → 1,000
O(2n) → 2,000
↑ 2배 차이
================
↓ 2배 차이
n = 1,000,000
O(n) → 1,000,000
O(2n) → 2,000,000

 

위의 예시를 보면 데이터의 크기와 상관 없이, 여전히 2배차이 입니다.

즉O(n)과 O(2n)은 증가 형태가 완전히 같습니다.

 

입력이 10배 늘어나면 실행 시간도 10배 늘어납니다.

2배는 그냥 속도가 조금 더 느릴 뿐, 증가 패턴 자체는 동일합니다.

그래서 이 둘을 O(n)으로 묶습니다.

 

하지만 O(n²)는 완전히 다릅니다. 똑같이 비교 해보겠습니다.

n = 1,000
O(n) → 1,000
O(n²) → 1,000,000
================
n = 1,000,000
O(n) → 1,000,000
O(n²) → 1,000,000,000,000

 

O(n²)은 결과가 차원이 다릅니다. O(n)은 1,000배가 증가했지만 O(n²)은 1,000,000배 증가했습니다.

이것이 바로 "증가 속도"의 차이입니다.

 

2배는 단순히 직선처럼 증가하는 것 뿐이지만, O(n²)는 곡선처럼 급격히 증가합니다.

 

O(1) 상수

O(1)은 주로 배열에서 한 개의 데이터를 찾을때 사용 되며, 데이터의 크기와 상관 없이 실행 시간이 일정합니다.

int value = arr[5];

 

O(n) 선형 

선형은 입력 크기와 비례하는 실행 시간을 가지며, 주로 선형 탐색 알고리즘에서 사용 됩니다 배열에서 특정 값을 비교하기 위해서는, 배열의 처음부터 끝까지 하나씩 확인하며 비교해야 합니다. 즉 데이터의 크기가 10개라면 최대 10번, 크기가 1,000,000개라면 최대 1,000,000번을 비교할 수 있습니다.

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

 

O( n² ) 제곱

O( n² ) 은 데이터 전체를 두 번 반복해서 처리하는 구조입니다. 즉 n * n 형태로 연산이 증가하며, 대표적인 예시로는 이중 반복문이 있습니다.

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

 

O(log n) 로그  

int left = 0;
int right = arr.length - 1;

while (left <= right) {
    int mid = (left + right) / 2;

    if (arr[mid] == 5) {
        count++;
        break;
    } else if (arr[mid] < 5) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

O(log n)는 입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가 합니다. 주로 이진 탐색(Binary Search)에서 많이 사용되며 이는 정렬된 배열에서만 사용할 수 있는 탐색 방법입니다. 이 방법의 핵심은 한 번 비교할 때마다 탐색 범위를 절반으로 줄이는 것 입니다.

 

예를 들어 크기가 1,000,000인 정렬된 배열에서 45,000이라는 값을 찾는다고 가정 하겠습니다.

선형 탐색을 사용하면 최악의 경우 1,000,000번 비교해야 합니다.

 

하지만 이진탐색 알고리즘은 아래와 같이 동작합니다.

1. 가운데 값 확인

2. 찾는 값이 더 크면 오른쪽 절반만 탐색 / 더 작으면 왼쪽 절반만 탐색

3. 과정 반복

 

위 과정은 탐색 범위를 매번 1/2로 줄이기 때문에, 필요한 비교 횟수는 약 20번 정도입니다.

위와 같이 값의 비교를 통해 데이터를 절반으로 나누기에 반드시 정렬이 돼있어야 합니다.

 

그러면 항상 이진탐색 방법을 이용하면 좋은걸까요? 그렇지는 않습니다.

만약 한 번만 검색한다면 정렬 비용(O(n log n))이 더 클 수 있기 때문에, 선형 탐색 알고리즘을 이용하는 것이 좋고, 여러번 검색이 필요하다면 미리 정렬 후 이진 탐색이 유리합니다. 즉 선택 기준은 "검색 횟수"와 "정렬 여부"입니다.

 

O(n log n) 로그 선형

O(n log n)은 데이터 전체를 log(n) 단계에 걸쳐 반복 처리하는 구조입니다. 즉 데이터의 개수(n)를 로그 단계(log n)동안 반복합니다. 주로 병합 정렬(Merge Sort) 알고리즘에서 이용 되며, 아래 예시와 함께 살펴 보겠습브니다.

 

예시로 총 8개의 데이터가 있다고 가정하겠습니다. 동작 원리는 아래와 같습니다.

- 배열을 계속 반으로 나눈다(log n단계)

- 다시 정렬하면서 합친다(각 단계마다 n번 처리)

 

위의 이미지처럼 분할 단계에서는 (log n)이지만 병합 단계에서는 매 단계마다 전체 n개의 데이터를 처리하기 때문에 전체 시간 복잡도는 O(n log n)입니다.