Algorithm

[크래프톤 정글 ] 시간 복잡도

하루이2222 2024. 9. 20. 11:39

시간 복잡도(Time Complexity)는 알고리즘의 효율성을 측정하는 중요한 지표로, 입력 크기(input size)에 따라 알고리즘이 실행되는 시간의 증가율을 나타낸다. 시간 복잡도는 알고리즘이 처리해야 하는 작업량이 어떻게 증가하는지를 수학적으로 분석하여 표현하며, 주로 "빅 오 표기법(Big-O notation)"으로 나타낸다.

1. 빅 오 표기법(Big-O Notation)

빅 오 표기법은 입력 크기 ( n )에 대해 알고리즘의 실행 시간이 최악의 경우 어떻게 증가하는지를 설명한다. 이 표기법은 다음과 같은 형태로 사용된다:

  • ( O(1) ): 상수 시간 복잡도
  • ( O(log n) ): 로그 시간 복잡도
  • ( O(n) ): 선형 시간 복잡도
  • ( O(n log n) ): 로그 선형 시간 복잡도
  • ( O(n^2) ): 이차 시간 복잡도
  • ( O(2^n) ): 지수 시간 복잡도
  • ( O(n!) ): 팩토리얼 시간 복잡도

1.1. 상수 시간 복잡도 ( O(1) )

상수 시간 복잡도는 입력 크기에 상관없이 일정한 시간이 걸리는 경우를 의미한다. 예를 들어, 배열의 특정 인덱스에 접근하는 작업은 ( O(1) )이다.

def get_first_element(arr):
    return arr[0]  # 항상 일정한 시간이 걸림

1.2. 로그 시간 복잡도 ( O(log n) )

로그 시간 복잡도는 입력 크기가 커질수록 실행 시간이 느리게 증가하는 경우를 의미한다. 주로 이진 탐색에서 나타난다.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

1.3. 선형 시간 복잡도 ( O(n) )

선형 시간 복잡도는 입력 크기에 비례하여 실행 시간이 증가하는 경우를 의미한다. 배열의 모든 요소를 합산하는 작업이 대표적이다.

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

1.4. 로그 선형 시간 복잡도 ( O(n log n) )

로그 선형 시간 복잡도는 주로 효율적인 정렬 알고리즘에서 나타난다. 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 그 예이다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

1.5. 이차 시간 복잡도 ( O(n^2) )

이차 시간 복잡도는 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 경우를 의미한다. 흔히 보폭이 큰 중첩 반복문에서 나타난다. 버블 정렬(Bubble Sort)이 그 예이다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

1.6. 지수 시간 복잡도 ( O(2^n) )

지수 시간 복잡도는 입력 크기가 증가할 때 실행 시간이 매우 빠르게 증가하는 경우를 의미한다. 피보나치 수열의 재귀적 구현이 그 예이다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

1.7. 팩토리얼 시간 복잡도 ( O(n!) )

팩토리얼 시간 복잡도는 입력 크기가 증가함에 따라 실행 시간이 매우 가파르게 증가하는 경우를 의미한다. 예를 들어, N-Queen 문제의 완전 탐색(Brute Force) 방식이 여기에 해당된다.

# N-Queen 문제의 완전 탐색 방식은 보통 이렇게 구현하지 않으나, 설명을 위해 팩토리얼 시간 복잡도의 예로 들 수 있음.

2. 시간 복잡도의 계산 방법

2.1. 기본 연산의 수 계산

시간 복잡도를 계산하기 위해서는 주어진 입력에 대해 수행해야 하는 기본 연산의 수를 계산한다. 기본 연산은 문제의 해결에 직접 기여하는 연산으로, 반복문에서의 비교, 할당, 함수 호출 등이 포함된다.

예를 들어, 단순한 반복문에서의 시간 복잡도는 다음과 같이 계산할 수 있다:

def linear_function(n):
    for i in range(n):
        print(i)

위 함수는 ( n )번 반복하므로 시간 복잡도는 ( O(n) )이다.

2.2. 중첩 반복문의 시간 복잡도

중첩 반복문에서는 각각의 반복문이 전체 시간 복잡도에 어떻게 기여하는지를 분석해야 한다.

def quadratic_function(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

위 함수는 ( n times n )번 반복하므로 시간 복잡도는 ( O(n^2) )이다.

2.3. 재귀 함수의 시간 복잡도

재귀 함수의 시간 복잡도는 재귀 호출의 깊이와 각 호출에서 수행되는 연산의 수를 고려하여 계산된다. 재귀 호출은 종종 분할정복(Divide and Conquer) 알고리즘에서 사용되며, 이러한 알고리즘의 시간 복잡도는 마스터 정리를 통해 분석할 수 있다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

merge_sort의 시간 복잡도는 ( T(n) = 2T(n/2) + O(n) )으로 계산되며, 이는 ( O(n log n) 로 평가된다.

3. 최선, 평균, 최악의 시간 복잡도

시간 복잡도는 종종 세 가지 측면에서 분석된다:

  • 최선의 경우 시간 복잡도(Best Case): 알고리즘이 최소한의 작업을 수행할 때의 시간 복잡도. 예: 이미 정렬된 배열에 대해 퀵 정렬의 최선의 경우는 ( O(n log n) )이다.
  • 평균 시간 복잡도(Average Case): 다양한 입력에 대해 알고리즘이 수행하는 평균적인 작업량. 예: 퀵 정렬의 평균 시간 복잡도는 ( O(n log n) )이다.
  • 최악의 경우 시간 복잡도(Worst Case): 알고리즘이 최대의 작업을 수행해야 할 때의 시간 복잡도. 예: 퀵 정렬의 최악의 경우 시간 복잡도는 ( O(n^2) )이다.

4. 알고리즘의 비교 및 최적화

시간 복잡도를 이해하는 것은 알고리즘의 성능을 평가하고 최적화하는 데 필수적이다. 입력 크기가 커질수록 시간이 급격히 증가하는 알고리즘은 효율적이지 않다. 따라서 개발자는 알고리즘을 설계할 때 시간 복잡도를 고려해야 하며, 가능한 효율적인 알고리즘을 선택해야 한다.

예를 들어, 정렬 알고리즘을 선택할 때는 입력 크기와 데이터의 특성에 따라 선택이 달라질 수 있다. 작은 입력에 대해서는 단순한 알고리즘(예: 삽입 정렬)을 사용할 수 있지만, 큰 입력에 대해서는 ( O(n log n) ) 복잡도의 알고리즘(예: 병합 정렬)을 사용하는 것이 좋다.

5. 4-Queen 문제 에서의 복잡도

N-Queen 문제는 N×N 크기의 체스판 위에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 방법을 찾는 문제이다. 이 문제는 고전적인 백트래킹(Backtracking) 문제로 잘 알려져 있으며, 가능한 모든 경우를 탐색해야 하므로 탐색 알고리즘의 효율성이 중요하다.

N-Queen 문제의 기본 개념

  • 목표: N×N 체스판에 N개의 퀸을 배치하되, 모든 퀸이 서로를 공격하지 않도록 한다.
  • 조건: 퀸은 같은 행, 열, 대각선 상에서 다른 퀸을 공격할 수 있다. 따라서 어떤 행에 퀸을 배치하면, 그 행과 같은 열, 같은 대각선(좌상↔우하, 좌하↔우상)에 다른 퀸이 위치할 수 없다.

백트래킹을 사용한 N-Queen 문제 해결

백트래킹은 가능한 모든 후보군을 탐색하는 알고리즘이다. N-Queen 문제의 경우, 체스판의 각 행에 퀸을 하나씩 배치해 나가면서 조건에 맞지 않으면 되돌아가고, 조건에 맞으면 다음 퀸을 배치하는 방식으로 문제를 해결한다.

알고리즘 개요

  1. 첫 번째 행부터 마지막 행까지 각 행에 퀸을 하나씩 배치한다.
  2. 현재 퀸을 배치할 수 없는 위치가 나오면, 이전 행으로 돌아가 다른 위치에 퀸을 배치해 본다.
  3. 모든 퀸이 배치될 수 있는 경우, 가능한 하나의 해를 찾았다. 이 과정을 반복하여 모든 해를 찾는다.

백트래킹의 동작 과정

  1. 배치 시도: 퀸을 첫 번째 행부터 시작하여 차례로 각 행에 배치한다.
  2. 유효성 검사: 퀸을 배치할 때마다 이전에 배치된 퀸들과의 위치를 비교하여 같은 열이나 대각선에 위치하는지 확인한다.
  3. 백트래킹: 만약 퀸을 배치할 수 없는 경우, 이전 단계로 돌아가 다른 위치에 퀸을 배치해본다. 이 과정을 되풀이하여 가능한 모든 해를 찾는다.

예제: 4-Queen 문제

행/열:   0   1   2   3
         -----------------
      0 |   | Q |   |   |
      1 |   |   |   | Q |
      2 | Q |   |   |   |
      3 |   |   | Q |   |

위의 예제는 4×4 체스판에 4개의 퀸을 배치한 결과 중 하나이다. 각 퀸이 서로 공격하지 않도록 배치되어 있다.

시간 복잡도 분석

전체 탐색 경우의 수

N-Queen 문제는 각 행에 퀸을 하나씩 배치하는 방식이다. 따라서 첫 번째 행에는 N가지 선택이 있고, 두 번째 행에는 남은 N-1가지 선택이 있으며, 이런 식으로 진행된다. 하지만, 이 문제는 모든 가능한 조합을 고려해야 하므로 전체 탐색의 경우의 수는 다음과 같이 계산된다.

  1. 첫 번째 퀸을 N개의 가능한 위치 중 하나에 배치한다.
  2. 두 번째 퀸을 (N-1)개의 가능한 위치 중 하나에 배치한다.
  3. 이 과정이 반복된다.

탐색 공간의 크기는 최악의 경우, 퀸을 놓을 수 있는 모든 위치를 고려해야 하므로 전체 경우의 수는 N^N이 된다. 그러나 백트래킹을 통해 유효하지 않은 경로를 일찍 차단하므로 실제로 탐색하는 경우의 수는 더 줄어든다.

백트래킹의 시간 복잡도

백트래킹을 사용할 때, 최악의 경우 탐색해야 하는 노드 수는 N! (N 팩토리얼)로 추정할 수 있다. 이는 모든 퀸을 다른 행에 놓아야 하므로, 각 행마다 가능한 열을 탐색하기 때문이다. 그러나 실제 시간 복잡도는 다음과 같이 분석할 수 있다.

  1. 탐색 공간: 각 행에 대해 N가지 선택이 가능하다. 따라서 탐색해야 하는 총 상태의 수는 O(N!)이 된다.

  2. 제약 조건 확인: 각 상태에서 유효성 검사를 수행하는데, 이 과정은 O(N) 시간이 걸린다. 왜냐하면, 새로 추가된 퀸이 이전에 배치된 퀸들과 같은 열이나 대각선에 있는지 확인해야 하기 때문이다.

따라서 전체 시간 복잡도는 O(N! * N)이 된다. 이는 매우 빠르게 증가하는 비효율적인 시간 복잡도로, N이 커질수록 계산 비용이 크게 늘어난다.

최적화

N-Queen 문제는 위에서 설명한 기본 백트래킹 알고리즘 외에도 다양한 최적화 기법을 적용할 수 있다. 예를 들어, 대각선에 대해 미리 가능한 위치를 계산하거나, 비트 마스크를 사용해 퀸의 배치를 효율적으로 관리하는 방법이 있다. 이러한 최적화를 통해 실질적인 실행 시간을 줄일 수 있다.

결론

  • 기본 백트래킹 알고리즘: 시간 복잡도는 O(N! * N)으로 매우 비효율적이다.
  • 탐색 공간: 백트래킹을 통해 일부 경로를 차단하더라도, 최악의 경우 여전히 매우 많은 경우의 수를 탐색해야 한다.
  • 최적화: 특정 최적화 기법을 적용하면 실행 시간을 줄일 수 있으나, 문제의 근본적인 시간 복잡도는 여전히 N!에 의해 좌우된다.

'Algorithm' 카테고리의 다른 글

[크래프톤 정글] 우선순위 큐  (0) 2024.09.20
[크래프톤 정글] 힙트리  (1) 2024.09.20
[크래프톤 정글 ] 스택과 큐  (0) 2024.09.20
[크래프톤정글] 파이썬의 메모리 관리  (0) 2024.09.20
[크래프톤 정글 ] 트리 란 ?  (0) 2024.09.20

'Algorithm'의 다른글

  • 현재글[크래프톤 정글 ] 시간 복잡도

관련글

티스토리툴바