[코딩테스트] 시간복잡도

---

시간복잡도 (Time Complexity)

입력 크기에 따라 알고리즘이 실행되는 데 걸리는 시간을 함수로 나타낸으로, 간단하게 말하자면 알고리즘이 빠르거나 느리게 수행되는지에 대한 평가 기준이다. 시간복잡도가 중요한 이유는 코드의 효율성을 분석 할 수 있기 때문이다.

코딩테스트에서 시간복잡도를 생각하지 않는다면, 제 시간안에 문제 해결을 못 할 수도 있다. 열심히 문제를 분석하고 코드를 작성하고 테스트했지만, 효율성에서 떨어지게 된다면 원점에서 다시 생각해야 될 수 있기 때문이다. 또한 시간제한이 있는 코딩테스트에서 다시 원점에서 다시 생각하고 코드를 작성한다는 것은 시간조절에 실패하고 치명적이기 때문이다.
 그렇기에 시간 복잡도는 무엇인지 알아보고자 한다.

---

빅오표기법 (Big-O Notation)

시간 복잡도를 표현할 때 사용하는 표기법으로, 가장 큰 차수의 항만 고려하여 효율성을 간단하게 나타내는 방법으로써 가령, 입력이 커질 때 성능에 가장 큰 영향을 주는 요소만을 표기하여 상수나 작은 항목은 생략하는 표기방법.

 

• 1. O(1) : 상수 시간 복잡도 : 입력 크기에 관계없이 항상 일정한 시간이 걸림.
• 2. O(log n): 로그 시간 복잡도 : 입력이 증가해도 시간이 매우 느리게 증가. 이진 탐색 알고리즘에서 나타남.
• 3. O(n) : 선형 시간 복잡도 : 입력이 커질수록 시간이 입력 크기에 비례하여 증가.
• 4. O(n log n) : 로그 선형 시간 복잡도 : 병합 정렬, 퀵 정렬 같은 효율적인 정렬 알고리즘에서 나타남.
• 5. O(n^2) : 이차 시간 복잡도 : 입력이 커질수록 시간이 제곱에 비례하여 증가함.
  선택 정렬이나 버블 정렬과 같은 알고리즘에서 나타남.
• 6. O(2^n) : 지수 시간 복잡도 : 입력이 커질수록 시간이 지수적으로 증가. 피보나치 수열의 비효율적인 재귀 구현에서 볼 수 있음.

---

예시코드

1. O(1) — 상수 시간 복잡도
상수 시간 복잡도를 가지는 알고리즘은 입력 크기에 관계없이 항상 일정한 시간이 소요됨.
가령 배열의 첫번째 요소를 접근하는 연산은 O(1) 가 됨.

public int getFirstElement(int[] array) {
    return array[0]; // 입력 크기와 관계없이 항상 한 번의 연산만 수행
}

 

2. O(log n) — 로그 시간 복잡도
로그 시간 복잡도는 이진 탐색(Binary Search) 같은 알고리즘에서 발생하며,
입력이 증가해도 실행 시간이 매우 느리게 증가함.
Tip : 이진 탐색은 매 단계마다 검색 범위를 절반으로 줄이므로 시간 복잡도가 O(log n) 임.

public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (array[mid] == target) {
            return mid; // 목표 요소를 찾은 경우
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 목표 요소를 찾지 못한 경우
}

3. O(n) — 선형 시간 복잡도
선형 시간 복잡도는 입력이 커질수록 시간이 입력 크기에 비례하여 증가하는 경우.
가령 배열의 모든 요소를 한 번씩 출력하는 경우.
아래 코드의 시간 복잡도는 배열의 크기 n에 따라 O(n) 임.

public void printAllElements(int[] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]); // 각 요소를 출력
    }
}

4. O(n^2) — 이차 시간 복잡도
이차 시간 복잡도는 두 개의 중첩된 루프가 있을 때 발생함.
가령 버블정렬(Bubble Sort) 알고리즘에서 모든 요소를 반복하면서 정렬하는 경우.
Tip : 버블 정렬은 두 개의 중첩된 루프를 사용하여 각 요소를 비교하므로 시간 복잡도가 O(n^2) 임.

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Swap array[j] and array[j + 1]
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

5. O(2^n) — 지수 시간 복잡도
지수 시간 복잡도는 재귀 호출이 폭발적으로 증가하는 경우 발생함.
가령 피보나치 수열을 재귀로 계산하는 알고리즘은 지수 시간 복잡도를 가짐.
Tip : 아래 코드의 fibonacci(n)을 계산할 때마다 이전 두 값을 다시 계산하므로, 시간 복잡도는 O(2^n) 임.

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

---

정리 : 시간복잡도는 알고리즘의 효율성을 측정하는 기준. 표기법은 빅오표기법이 있음 Big-O Notation. 

---