빅오 표기법: 시간 복잡도

Java 코드 최적화

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

시간 복잡도란?

시간 복잡도: 입력 크기에 따라 실행 시간이 어떻게 증가하는지 측정
"데이터가 10배 늘어나면 어떻게 될까?"라는 질문에 답하는 데 도움
절대적인 시간에 초점을 맞추지 않음

빅오 표기법

최악의 경우를 설명하는 수학적 표기법입니다.

일반적인 복잡도 클래스:

O(1): 상수 시간 - 크기와 무관

O(1) 이해하기

O(1) 연산의 예로 ArrayList의 get()이 있습니다

Strings를 저장하는 ArrayList의 내부(단순화된) 구현:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

빅오 표기법

최악의 경우를 설명하는 수학적 표기법

일반적인 복잡도 클래스:

O(1): 상수 시간 - 크기와 무관
O(n): 선형 시간 - 입력 크기에 비례해 증가

O(n) 이해하기

ArrayList의 contains()에 대한 비슷한 예시입니다

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

빅오 표기법

최악의 경우를 설명하는 수학적 표기법

일반적인 복잡도 클래스:

O(1): 상수 시간 - 크기와 무관
O(n): 선형 시간 - 입력 크기에 비례해 증가
O(n²): 2차 시간 - 입력 크기의 제곱에 비례해 증가

2차 복잡도의 실제 예시

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

시간 복잡도가 중요한 이유

입력 크기의 영향:

O(1): 1,000 -> 1,000,000개 항목 = 동일한 시간!
O(n): 1,000 -> 1,000,000개 항목 = 1,000배 느려짐
O(n²): 1,000 -> 1,000,000개 항목 = 1,000,000배 느려짐

Screenshot 2025-05-10 at 2.27.06 PM.png

연습해 봅시다!

Java 코드 최적화