시간복잡도, 공간복잡도

JAVA로 구현하는 알고리즘과 디자인 패턴 공부: 시간 복잡도와 공간 복잡도

1. 왜 성능 분석이 필요한가요? 🤔

"어떤 코드가 더 좋은 코드일까?"라는 질문에 어떻게 답할 수 있을까요? 단순히 코드를 실행시켜서 시간을 재는 방법도 있지만, 이 방법은 컴퓨터의 성능, 사용 언어, 심지어 실행 시점의 시스템 상태에 따라서도 결과가 달라집니다.

그래서 우리는 **"입력 데이터의 크기(n)가 커질수록 알고리즘의 실행 시간/사용 공간이 얼마나 증가하는가?"**를 나타내는 객관적인 지표를 사용합니다. 이것이 바로 **복잡도 분석(Complexity Analysis)**이며, 이때 빅오(Big-O) 표기법을 사용합니다.

빅오(Big-O) 표기법은 알고리즘 성능의 **최악의 경우(Upper Bound)**를 나타내는 가장 보편적인 방법입니다. "아무리 상황이 나빠져도 이 성능보다는 오래 걸리지 않는다"는 의미를 담고 있어 알고리즘의 효율성을 판단하는 중요한 기준이 됩니다.

---

2. 시간 복잡도 (Time Complexity) 🕰️

개념: 알고리즘을 실행하는 데 걸리는 시간을 연산의 실행 횟수로 표현한 것입니다. 입력 데이터의 크기 n에 대해 연산 횟수가 어떻게 변하는지를 나타냅니다.

• 주요 빅오 표기법 (빠른 순서대로):
  • O(1) (Constant Time): 최고의 성능! 입력 데이터 크기에 상관없이 항상 일정한 수의 연산을 수행합니다.
  • Java

     

    // 배열의 특정 인덱스에 접근하는 것은 데이터 크기와 무관하게 즉시 실행됩니다.
    int getFirst(int[] arr) {
        return arr[0]; // 연산 1번
    }
    

  • O(logn) (Logarithmic Time): 매우 효율적! 연산이 한 번 진행될 때마다 탐색해야 할 데이터의 양이 절반씩 줄어듭니다. 지난 시간에 배운 **이진 탐색(Binary Search)**이 대표적입니다.
  • Java

     

    // 이진 탐색은 매번 탐색 범위를 반으로 줄여나갑니다.
    // 데이터가 100개면 약 7번, 1000개여도 약 10번만에 값을 찾습니다.
    

  • O(n) (Linear Time): 좋은 성능. 입력 데이터 크기 n에 비례하여 연산 횟수가 증가합니다. **선형 탐색(Linear Search)**처럼 배열의 모든 요소를 한 번씩 확인하는 경우가 해당됩니다.
  • Java

     

    // 배열의 모든 요소를 한 번씩 순회하며 값을 찾습니다.
    int findValue(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) { // n번 연산
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
    

  • O(nlogn) (Log-Linear Time): 효율적인 정렬 알고리즘들이 여기에 속합니다. 대표적으로 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)이 있습니다. n개의 데이터를 처리하기 위해 전체를 여러 번 훑지만, 그 횟수가 logn에 비례합니다.
  • O(n2) (Quadratic Time): 데이터 크기가 커지면 성능이 급격히 나빠집니다. 이중 반복문 구조에서 주로 나타나며, 지난 시간에 배운 버블 정렬, 선택 정렬이 여기에 해당합니다.
  • Java

     

    // 이중 for문으로 배열의 모든 요소 쌍을 비교합니다.
    void printAllPairs(int[] arr) {
        for (int i = 0; i < arr.length; i++) {       // n번 반복
            for (int j = 0; j < arr.length; j++) {   // n번 반복
                System.out.println(arr[i] + ", " + arr[j]); // 총 n * n 번 실행
            }
        }
    }
    

  • O(2n) (Exponential Time): 매우 비효율적! 데이터 크기가 조금만 커져도 실행 시간이 기하급수적으로 늘어납니다. 대표적으로 재귀로 구현한 피보나치 수열 계산이 있습니다.

---

3. 공간 복잡도 (Space Complexity) 💾

개념: 알고리즘이 실행되는 동안 사용하는 추가적인 메모리 공간의 양을 나타냅니다. 입력 데이터 자체를 저장하는 공간은 보통 제외하고, 알고리즘이 문제를 풀기 위해 보조적으로 할당하는 메모리를 기준으로 계산합니다.

• O(1) (Constant Space): 입력 데이터 크기와 상관없이 항상 고정된 크기의 추가 메모리를 사용합니다.
• Java

   

  // 두 변수의 값을 교환하는 데에는 'temp'라는 하나의 추가 공간만 필요합니다.
  void swap(int a, int b) {
      int temp = a;
      a = b;
      b = temp;
  }
  

• O(n) (Linear Space): 입력 데이터 크기 n에 비례하는 추가 메모리를 사용합니다.
• Java

   

  // 입력 배열과 똑같은 크기의 배열을 새로 만들어 반환합니다.
  int[] copyArray(int[] arr) {
      int[] newArr = new int[arr.length]; // n 크기의 추가 공간 할당
      for (int i = 0; i < arr.length; i++) {
          newArr[i] = arr[i];
      }
      return newArr;
  }
  // 재귀 호출은 호출 스택(Call Stack)에 메모리를 사용하는데,
  // 재귀의 깊이가 n에 비례하면 공간 복잡도는 O(n)이 됩니다.
  // (지난 시간의 DFS가 이런 경우에 해당될 수 있습니다.)
  

---

4. 실제 활용 예 (feat. Spring Framework)

개발자는 시간/공간 복잡도를 끊임없이 저울질하며 트레이드오프(Trade-off) 관계 속에서 최적의 결정을 내립니다.

• 상업적 활용:
  • ArrayList vs. LinkedList: ArrayList는 인덱스 접근이 $O(1)$이지만, 중간에 데이터를 삽입/삭제하면 $O(n)$이 걸립니다. 반면 LinkedList는 삽입/삭제가 $O(1)$이지만, 특정 원소를 탐색하려면 $O(n)$이 걸립니다. 데이터를 어떻게 사용할지에 따라 자료구조 선택이 달라지며, 이는 복잡도에 기반한 결정입니다.
  • 데이터베이스 인덱스(Index): 인덱스는 특정 컬럼의 데이터를 B-Tree와 같은 자료구조로 미리 정렬해두는 것입니다. 덕분에 수억 건의 데이터 속에서도 $O(n)$의 풀스캔(Full Scan) 대신 $O(\log n)$의 빠른 속도로 데이터를 검색할 수 있습니다.
• Spring Framework에서의 활용:
  • 페이지네이션(Pagination): 게시판에 수만 개의 글이 있을 때, 모든 글을 한 번에 조회(findAll())하면 $O(n)$의 시간과 메모리가 필요하여 서버가 다운될 수 있습니다. Spring Data JPA의 Pageable 객체는 "20개씩 끊어서 1페이지를 보여줘"라는 요청을 처리합니다. 이는 전체 데이터(n)의 크기와 상관없이 고정된 수(k)의 데이터만 다루므로 $O(1)$의 성능을 보장하여 시스템을 안정적으로 만듭니다.

---

5. 문제 제시 및 답변

개념을 잘 이해했는지 확인해볼 시간입니다! 🧐

문제: 주어진 정수 배열에 중복된 값이 있는지 확인하는 함수가 있습니다. 아래 두 가지 구현 방식의 시간 복잡도와 공간 복잡도를 각각 분석해보세요.

Java

 

// 방식 1: 이중 반복문 사용
boolean hasDuplicates_A(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                return true;
            }
        }
    }
    return false;
}

// 방식 2: HashSet 사용
boolean hasDuplicates_B(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int value : arr) {
        if (set.contains(value)) {
            return true;
        }
        set.add(value);
    }
    return false;
}

답변:

• 방식 1 (이중 반복문)
  • 시간 복잡도: O(n2) - n개의 원소를 가진 바깥쪽 루프 안에서, 안쪽 루프가 평균적으로 약 n/2번 회전합니다. 빅오 표기법으로는 상수를 무시하므로 $O(n \times n) = O(n^2)$가 됩니다.
  • 공간 복잡도: O(1) - 추가적인 데이터 구조를 사용하지 않고, 반복문을 위한 변수 i, j 등 고정된 양의 메모리만 사용합니다.
• 방식 2 (HashSet 사용)
  • 시간 복잡도: O(n) - 배열의 모든 원소를 한 번만 순회합니다. HashSet의 contains와 add 연산은 평균적으로 $O(1)$의 시간 복잡도를 가지므로, 총 시간 복잡도는 $O(n \times 1) = O(n)$이 됩니다.
  • 공간 복잡도: O(n) - HashSet에 원소를 저장해야 합니다. 최악의 경우 (중복이 하나도 없을 때) 배열의 모든 원소 n개를 set에 저장해야 하므로 n에 비례하는 추가 공간이 필요합니다.

결론: 방식 2는 추가 메모리(공간)를 사용하는 대신, 비교할 수 없을 정도로 빠른 실행 시간(시간)을 얻었습니다. 이것이 바로 **"시간과 공간의 트레이드오프"**를 보여주는 대표적인 예입니다.