[Algorithm] 시간복잡도에 대해 알아보기

아무리 사교육을 흔들어 제껴도 수학을 70점을 넘어본 적이 없는 내가 너무 어려워서 작성하는 글

사실 log도 뭔지 잘 모름... 어카지

로그(log) : 어떤 수를 만들기 위해 밑을 몇 번 거듭제곱해야 하는지를 나타내는 수학적 개념 
\(a^x = n \) 에서 \(x\)를 \(log_a(n)\)로 표현한다.

1. 시간복잡도 정의

시간복잡도란 입력값(N)이 커질수록 알고리즘의 수행 시간이 얼마나 빨라지거나 느려지는지 확인하는 지표를 의미한다.

입력 크기 n이 증가함에 따라 연산 횟수가 증가하는 증가율(Growth Rate)를 수학적으로 표기한다. 이 증가율을 점근적 표기법(Aysmptotic Notation)을 사용하는데, 개발에선 대부분 빅오(Big-O)표기법을 가장 많이 사용한다.

표기법	기호	의미	용도
Big-O	O	최악의 경우(상한)	알고리즘의 성능 보장을 위해 가장 일반적으로 사용
Big-Omega	Ω	최선의 경우(하한)	알고리즘이 아무리 빨라도 이보단 느릴 수 없음을 나타냄
Big-Theta	θ	평균적인 경우	최선과 최악의 경우가 동일한 알고리즘에 사용

시간복잡도를 알면 어떤 것이 더 빠른 코드인지, 어디를 개선해야 하는지 판단할 수 있다.

 

2. 종류와 특징

주요 시간 복잡도는 입력크기 n에 대한 연산 횟수와 증가율에 따라 분류된다. 증가율이 낮을 수록(= 그래프가 가파르지 않을수록) 더 좋은 성능을 의미한다.

 

1. \(O(1)\)

• 명칭 : 상수 시간(Constant)
• 특징 : 입력 크기와 상관 없이 실행시간이 일정하며, 가장 빠름
• 예시 : 배열에서 인덱스를 통한 요소 접근, 해시 테이블 조회 - 상수

2. \(O(log n)\)

• 명칭 : 로그 시간(Logarithmic)
• 특징 : 입력 크기가 증가할 때 실행 시간은 매우 느리게 증가
• 예시 : 이진 탐색(Binary Search) - 이분 탐색

3. \(O(n)\)

• 명칭 : 선형 시간(Linear)
• 특징 : 입력 크기와 실행 시간이 정비례하여 증가함
• 예시 : for루프를 한번 돌며 배열 전체를 순회 - 한번 훑기

4. \(O(n \log n)\)

• 명칭 : 선형 로그 시간(Linearithmic)
• 특징 : \(O(n)\) 보다 느리지만 \(O(n^2) \) 보단 빠름. 실용적으로 좋은 성능으로 간주됨
• 예시 : 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) - 효율적 정렬

5. \(O(n^2)\)

• 명칭 : 제곱 시간(Quadratic)
• 특징 : 실행 시간이 입력 크기의 제곱에 비례하여 증가함. 느린 편
• 예시 : 이중 for 루프(Nested loops), 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort) - 두겹 반복

6. \(O(2^n)\)

• 명칭 : 지수 시간(Exponential)
• 특징 : 입력 크기가 조금만 커져도 실행 시간이 기하급수적으로 늘어남. 비효율적
• 예시 : 재귀를 이용한 파보나치 수열, 일부 Brute-Force 방식 - 작은 n에서만 사용

7. \(O(n!)\)

• 명칭 : 팩토리얼 시간(Factorial)
• 특징 : \(O(2^n)\) 보다 훨씬 빠르게 증가함. 매우 비효율적
• 예시 : 순열을 계산하는 모든 문제 - 작은 n에서만 사용

개발자는 일반적으로 \(O(n \log n)\) 이하의 시간 복잡도를 가진 알고리즘을 설계하거나 선택한다. \(O(n^2)\) 이상은 입력 크기가 작은 경우에만 허용된다.

 

3. 코드에서 시간복잡도 보는법

한줄 한줄이 중요한 것이 아닌, 전체 흐름이 N과 어떻게 관계되는지가 핵심이다.

1. 반복문이 몇겹인지 보기
2. 반복 범위가 N에 따라 변하는지 보기
3. 재귀 함수가 N을 어떻게 줄여가며 호출되는지 보기
4. 정렬이나 탐색이 섞여있다면 특성을 파악하기

예시

1️⃣ 반복문이 몇겹인가

\(O(n)\) : 반복문 한 겹

void printNum(int N) {
  for (int i = 0; i < N, i++) {
   System.out.println(i);  // 입력이 커지면 반복 횟수도 N만큼 증가
  }
}

 

\(O(n^2)\) : 반복문 두 겹

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

총 실행 횟수 : N * N =  \(O(n^2)\)

 

2️⃣ 반복 범위가 N에 따라 어떻게 변하는가

\(O(1)\) : 범위가 고정

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

입력 크기와 상관 없이 실행 횟수가 항상 100번 = \(O(1)\) 

 

\(O(log n)\) : 범위가 절반씩 줄어듦 = 이분 패턴

void halfLoop (int N) {
  while (N > 1) {
   N = N / 2;
  }
}

매번 입력을 반으로 줄인다. 이게 이진 탐색의 원리

 

3️⃣ 재귀 함수가 N을 어떻게 줄여가는가

\(O(n)\) : 한 단계씩 줄어드는 선형 재귀

void linearRecursion (int n) {
  if (n == 0) {
    linearRecursion(n-1);
  }
}

n → n-1 → n-2 → n-3 ..... → 0

n번 호출됨 = \(O(n)\)

 

\(O(log n)\)  : 이진 탐색 재귀

int binarySearch (int[] arr, int target, int left, int right) {
  if (left > right) return -1;
  
  int mid = (left + right) / 2;
  
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    // arr[mid]가 target보다 작다면 왼쪽에서 +1칸 이동
    return binarySearch(arr, target, mid + 1, right); 
  } else {
    // arr[mid]가 target보다 크면 오른쪽에서 -1칸 이동
    return binarySearch(arr, target, left, mid - 1);
  }
}

// 중앙으로 다가가는 느낌

탐색 범위가 매 재귀마다 절반으로 줄어든다.

 

 \(O(n \log n)\) : 병합 정렬 구조

병합정렬(=합병 정렬, Merge Sort)이란?

출처 : By Swfung8 - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961648

분할정복(Divide and Conquer)알고리즘 중 하나로, 데이터를 절반씩 쪼개어 원소가 하나만 남을때까지 나눈 뒤 정렬된 부분 리스트들을 다시 합치면서 전체 데이터를 정렬하는 알고리즘

• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우
• 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

---

🌷 반으로 계속 나누는 과정이 log n인 이유

\(log n\) = " N이 1이 될 때 까지 몇번을 반으로 잘라야 하는가? "

예를 들어,

• 16개라면
  16 → 8 → 4 → 2 → 1
  총 4번 잘렸으니까 log₂ 16 = 4
• 8개라면
  8 → 4 → 2 → 1
  총 3번 → log₂ 8 = 3

그러니까 병합 정렬은 배열을 log n번만큼 깊게 쪼개는 구조

 

🌷그런데 왜 n을 곱하는가?

 나누는 작업은 빠르지만 합치는 작업은 생각보다 많이 들기 때문

각 층에서 배열 전체를 다 스캔해야 한다.

👉 쪼개는 깊이는 log n
👉 하지만 “각 층마다” 합치는 데 O(n) 시간이 든다

실제로 이렇게:

• 맨 위 층: 8개 병합 → 8번 비교
• 그 아래 층: 4개 + 4개 → 총 8번 비교
• 그 아래 층: 2+2+2+2 → 총 8번 비교
• 그 아래 층: 1+1+1+1+1+1+1+1 → 총 8번 비교

즉, 각 층이 전부 n만큼의 일이 필요하다.

void mergeSort(int[] arr, int left, int right) {
  if (left > right) return;
  
  int mid = (left + right) / 2;
  
  // 문제를 반으로 나누는 부분 = 2개의 T(n/2)
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  
  // 병합 과정
  merge(arr, left, mid, right);
}

void merge(int[] arr, int left, int mid, int right) {

    int[] temp = new int[right - left + 1]; // 합친 결과를 담을 임시 배열
    int i = left;      // 왼쪽 덩어리 시작점
    int j = mid + 1;   // 오른쪽 덩어리 시작점
    int k = 0;         // 임시 배열 인덱스

    // 두 덩어리를 비교하며 작은 값부터 temp에 넣기
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }

    // 왼쪽 덩어리에 남은 요소가 있으면 그대로 복사
    while (i <= mid) {
        temp[k] = arr[i];
        i++;
        k++;
    }

    // 오른쪽 덩어리에 남은 요소가 있으면 그대로 복사
    while (j <= right) {
        temp[k] = arr[j];
        j++;
        k++;
    }

    // temp 배열 내용을 원래 arr로 돌려놓기
    for (int t = 0; t < temp.length; t++) {
        arr[left + t] = temp[t];
    }
}

재귀식: \(T(n)\) = \(2T(n/2)\) + \(O(n)\)  →  \(O(n \log n)\)

 

4️⃣ 여러 알고리즘(정렬, 탐색 등)이 섞여 있을 때 (합, 곱 판단)

• 순차적 합 :서로 따로 실행되는 블록은 더한다
• 중첩(합성) 곱 : 내부가 외부 횟수에 따라 반복되면 곱한다(ex. 두 중첩 for문)

A → B 순서로 실행(더하기 → 큰 쪽이 지배)

void mixed1 (int N) {
 for (int i = 0; i < N; i++); // O(N)
 for (int j = 0; j < N; j++); // O(N)
}
// → O(N)

 

중첩이면 곱하기

void mixex2 (int N, int M) {
  for (int i = 0; i < N; i++) { // O(N)
    for (int j = 0; j < M; j++) { // O(M)
      System.out.println("Hi!");
    }
  }
}
// → O(N * M)

 

섞인 정렬 구조 \( n \log n  + N →  n \log n \)

void sortAndPrint (int[] arr) {
  Arrays.sort(arr);   // O(N log N)
  for (int x : arr) { //  O(N)
    System.out.println(x);
  }
}
// 최종 : → O(N log N)

 

4. 왜 중요한가

1. 성능 예측 : 실제 코드를 실행하지 않고도 대규모 입력에 대한 성능을 예측하게 함
2. 알고리즘 선택 : 동일한 문제를 해결하는 여러 알고리즘 중 가장 효율적인 알고리즘을 선택하는 기준을 제공
3. 리소스 관리 : 서버 자원(CPU 시간 등) 사용을 최적화하여 비용을 절감하고 서비스 응답 시간을 개선할 수 있음

 

[참고 자료]

https://todaycode.tistory.com/45

시간 복잡도란?

https://adjh54.tistory.com/186

[Java/알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법 이해하기

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog