시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘이 입력 크기(n)에 따라 실행 시간을 얼마나 소비하는지를 분석하는 개념입니다. 빅오 표기법(Big-O Notation)을 사용하여 최악의 경우 실행 시간을 나타냅니다.

대표적인 시간 복잡도 종류

시간 복잡도	설명
O(1)	입력 크기와 관계없이 실행 시간이 일정함
O(log n)	입력 크기가 증가할수록 실행 시간이 로그(log) 형태로 증가함
O(n)	입력 크기에 비례하여 실행 시간이 증가함
O(n log n)	병합 정렬(Merge Sort)과 같은 정렬 알고리즘에서 나타남
O(n²)	중첩 루프가 있는 알고리즘 (버블 정렬, 선택 정렬 등)
O(2ⁿ)	피보나치 재귀 호출과 같은 경우
O(n!)	외판원 문제와 같은 조합 탐색

예제 코드로 시간 복잡도 분석

1. O(1) - 상수 시간

int GetFirstElement(int[] arr)
{
    return arr[0];  // 입력 크기와 관계없이 항상 1번 실행됨 (O(1))
}

배열 크기와 무관하게 실행 시간이 일정함

2. O(n) - 선형 시간

void PrintAllElements(int[] arr)
{
    foreach (var item in arr)
    {
        Console.WriteLine(item);  // n개의 요소를 출력 (O(n))
    }
}

입력 크기가 증가할수록 실행 횟수가 선형적으로 증가

3. O(n²) - 이차 시간 (중첩 루프)

void PrintPairs(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        for (int j = 0; j < arr.Length; j++)
        {
            Console.WriteLine(arr[i] + ", " + arr[j]);  // 두 개의 중첩 루프 (O(n²))
        }
    }
}

입력 크기 n이 커질수록 실행 횟수가 급격히 증가

4. O(log n) - 로그 시간 (이진 탐색)

int BinarySearch(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;  // 요소가 없음 (O(log n))
}

데이터 크기가 커질수록 검색 시간이 log n 만큼 줄어듦

5. O(n log n) - 로그-선형 시간 (병합 정렬)

int[] MergeSort(int[] arr)
{
    if (arr.Length <= 1)
        return arr;
    
    int mid = arr.Length / 2;
    int[] left = MergeSort(arr[..mid]);
    int[] right = MergeSort(arr[mid..]);
    
    return Merge(left, right);  // O(n log n) 시간 복잡도
}

재귀적으로 배열을 분할(로그 단계), 병합 시 선형 수행

6. O(2ⁿ) - 지수 시간 (피보나치 재귀)

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);  // O(2ⁿ)
}

입력 크기 n이 커질수록 함수 호출 횟수가 기하급수적으로 증가

Q&A

Q: 시간 복잡도란 무엇인가요?
A: 시간 복잡도는 알고리즘이 실행되는 속도를 나타내는 개념으로, 입력 크기(n)에 따라 실행 시간이 어떻게 변하는지를 분석하는 것입니다.

Q: 빅오 표기법(Big-O Notation)이란?
A: 빅오 표기법은 알고리즘의 성능을 최악의 경우를 기준으로 표현하는 방법입니다. 예를 들어, O(n)은 입력 크기에 비례하여 실행 시간이 증가함을 의미합니다.

Q: O(n log n)과 O(n²)의 차이는 무엇인가요?
A: O(n log n)은 정렬 알고리즘(예: 병합 정렬)에서 자주 나타나는 시간 복잡도로, O(n²)보다 훨씬 효율적입니다. O(n²)은 중첩 루프가 사용되는 알고리즘에서 발생하며, 입력 크기가 커질수록 실행 시간이 급격히 증가합니다.

Q: 어떤 알고리즘이 가장 빠른가요?
A: O(1) 알고리즘이 가장 빠르며, 그다음으로 O(log n), O(n) 순으로 성능이 좋습니다. 하지만 문제에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

결론

시간 복잡도를 고려하여 최적의 알고리즘을 선택하는 것이 중요합니다.
예를 들어, 정렬이 필요할 때 **버블 정렬(O(n²))보다는 병합 정렬(O(n log n))**을 선택하는 것이 효율적입니다.

Trend Info 2x