시간 복잡도에 대해 알아보자

시간 복잡도란 무엇인가?

시간 복잡도(Time Complexity)는 알고리즘의 실행 시간이 입력 데이터의 크기와 어떻게 변하는지를 수학적으로 분석한 것이다.
알고리즘의 효율성 및 최적화 등을 평가할 때 사용되며, 프로그램이 실행되는 데 걸리는 시간을 예측할 수 있다.

만약 컴퓨터가 초월적인 존재라 어떤 스파게티 코드를 짜든 항상 빠른 성능을 보여준다면 아무리 비효율적인 코드라고 해도 일단 작동된다면 사용했을것이다. (물론 가독성은 중요하다!)

하지만 컴퓨터는 한정된 공간과 연산 속도를 가졌고 이를 효율적으로 사용하기 위해서는 최적화된 알고리즘을 사용해야하며 이 알고리즘을 시간 복잡도를 통해 분석하는 것이다.

---

 

시간 복잡도 분석의 필요성

1. 성능 평가
   • 동일한 문제를 해결하는 여러 알고리즘 중, 실행 시간이 짧고 효율적인 알고리즘을 선택하는 데 도움을 준다.
2. 확장성 확인
   • 데이터 크기가 증가해도 성능을 유지할 수 있는지 확인할 수 있다.
3. 자원 최적화
   • 시간뿐만 아니라 메모리와 같은 다른 자원의 효율성을 평가하는 기반이 된다.

 

시간 복잡도의 표기법

시간 복잡도는 주로 "빅오 표기법(Big-O Notation)"으로 표현되며, 입력 크기 n이 증가할 때 알고리즘의 실행 시간의 증가율을 나타낸다. 빅 O 표기법의 주요 유형은 다음과 같다.

 

1. O(1) : 상수 형태

• 입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우.
• 예: 배열의 특정 인덱스에 접근.

int getValue(int arr[], int index) {
    return arr[index]; // O(1) 어떤 경우에서도 한번 실행
}

 

2. O(log n) : 로그 형태

• 입력 크기가 커질수록 실행 시간이 로그에 비례해 증가.
• 예: 이진 탐색.

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    } // log n 만큼 실행
    return -1;
}

 

3. O(n) : 선형

• 입력 크기에 비례해 실행 시간이 증가.
• 예: 배열 전체를 탐색.

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) return i;
    } // n 만큼 반복하여 실행
    return -1;
}

 

4. O(n log n) : 선형 로그

• 데이터 크기에 로그를 곱한 비율로 증가.
• 예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).

void mergeSort(int arr[], int left, int right) {
    // Merge Sort Implementation
}

 

5. O(n^c) : 다차 형태

 

• 입력 크기에 대해 제곱 비율로 실행 시간이 증가.
• 예: 중첩 반복문.

 

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        // O(n^2)
    }
}

 

6. O(c^n) : 지수 형태

• 입력 크기가 증가할 때 실행 시간이 지수적으로 증가.
• 예: 재귀적 해결 방식이 많은 피보나치 계산.

 

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

 

7. O(n!) : 팩토리얼 형태

• 입력 크기가 팩토리얼 형태로 증가.
• 예 : 전수조사(브루트 포스)

 

시간 복잡도 분석 방법

1. 가장 많이 실행되는 명령어 식별

• 반복문, 조건문 등 알고리즘에서 실행 횟수가 많은 부분을 찾는다.

2. 입력 데이터의 크기 확인

• 입력 크기 n과 실행 시간의 관계를 분석한다.

3. 최악의 경우 고려

• 알고리즘이 최악의 입력을 받았을 때의 실행 시간을 계산합니다. (개인적으로 계산할때 가장 중요한거)

4. 최고차항만 고려

• 빅오 표기법에서는 최고차항(가장 빠르게 증가하는 항)만 남기고 나머지는 생략한다.
• 예: 3n^2+5n+2→O(n2).

 

알고리즘의 시간 복잡도 예제

배열에서 최대값 찾기

// 배열에서 최고값 찾기 알고리즘
int findMax(int arr[], int size) {
    int maxVal = arr[0];
    for (int i = 1; i < size; ++i) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

• 반복문이 n번 실행되므로 시간 복잡도는 O(n).

---

 

마치며

시간 복잡도는 알고리즘의 효율성을 평가하는 핵심 개념이다.
효율적인 알고리즘을 설계하려면 다음을 고려해야 한다.

1. 입력 데이터의 크기가 커질 경우를 대비하여 시간 복잡도를 분석.
2. 중복 계산이나 불필요한 연산을 줄이기 위한 최적화.

알고리즘의 시간 복잡도를 이해하고 설계에 반영하면, 프로그램의 성능을 크게 향상시킬 수 있다.

특히나 특히나 특히나 코딩을 배울때 본인이 배운 언어의 문법을 다 깨우쳤다면 컴퓨터 이론을 배우며 시간 복잡도 개념을 깨우쳐야 한다.

https://www.acmicpc.net/step/53

백준의 시간 복잡도 문제를 풀며 짜여진 코드의 시간 복잡도를 계산해보고 기존에 자신이 짠 코드의 시간 복잡도 또한 계산해보자. (본인은 수학 머리가 굳어버려 시간좀 걸렸다..) 아마 최적화된 알고리즘이 무엇인지 <자료구조 & 알고리즘>을 배우고 싶은 욕구가 생겨날 것이다.