Algorithmic Complexity

Algorithmic Complexity

알고리즘 복잡도는 프로그램이나 알고리즘이 문제를 해결할 때 소요하는 시간과 공간, 즉 컴퓨팅 자원의 사용량을 입력 크기에 따라 수학적으로 분석하는 방법이다. 이러한 분석을 통해 하드웨어나 구현 세부사항에 구애받지 않고 알고리즘의 근본적인 효율성을 평가할 수 있다.
여러 알고리즘 중 어떤 것이 더 효율적인지, 또는 주어진 알고리즘이 특정 문제를 해결하는 데 얼마나 많은 자원(시간, 메모리)이 필요한지를 수학적으로 표현한다. 알고리즘 복잡도를 이해하면 더 나은 프로그램을 설계하고 최적화하는 데 큰 도움이 된다.

알고리즘 복잡도 분석은 문제 해결 과정에서 효율적인 알고리즘 선택과 최적화를 가능하게 하며, 이를 통해 작은 규모의 데이터뿐 아니라 대규모 데이터 처리 시에도 실행 시간과 메모리 사용을 예측할 수 있다. 또한, 알고리즘 복잡도는 비효율적인 알고리즘을 사전에 식별하고 개선할 수 있는 기준을 제공하므로, 실제 응용 프로그램 개발이나 시스템 설계에서 매우 중요한 역할을 한다.

종합하면, 알고리즘 복잡도는 입력 크기에 따른 자원 소요를 수학적으로 표현하고 분석하는 도구로서, 상수, 로그, 선형, 이차, 지수 등의 다양한 복잡도 클래스로 구분된다.
이러한 분석은 효율적인 알고리즘 선택 및 시스템 최적화를 위한 핵심적인 지표 역할을 하며, 복잡도 표기법을 통해 비교와 예측이 용이하게 이루어진다.

알고리즘 복잡도는 효율적인 소프트웨어 개발을 위한 필수적인 개념이다.
시간 복잡도와 공간 복잡도를 이해하고 분석함으로써, 다양한 알고리즘 중에서 특정 문제에 가장 적합한 해결책을 선택할 수 있다. 하지만 이론적인 분석만으로는 충분하지 않으며, 실제 환경에서의 성능 테스트와 프로파일링도 함께 고려해야 한다.
알고리즘 복잡도는 알고리즘의 효율성을 예측하고 비교하는 데 도움을 주는 강력한 도구이지만, 실제 애플리케이션 개발에서는 코드의 가독성, 유지보수성, 개발 시간 등 다른 요소들도 함께 고려해야 한다.

복잡도의 기본 개념

알고리즘 복잡도는 보통 T(n)으로 표현되며, 여기서 n은 입력의 크기를 나타내고 T(n)은 기본 연산(상수 시간 소요 단계)의 총 횟수를 의미한다.
실제 처리 시간은 프로세서 속도, 컴파일러, 메모리 구조 등 다양한 요인에 따라 달라질 수 있지만, 복잡도 분석은 이러한 하드웨어적 차이를 배제하고 입력 크기 변화에 따른 근본적 성능 변화를 파악하는 데 집중한다.

알고리즘 복잡도는 크게 두 가지로 나뉜다:

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 실행하는 데 필요한 시간을 표현한다.
실제 시계 시간이 아니라, 입력 크기에 따른 연산 횟수의 함수로 표현된다.
시간 복잡도는 알고리즘의 ‘빠르기’를 측정하는 척도이다.

공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 실행하는 데 필요한 메모리의 양을 표현한다.
입력 크기에 따라 알고리즘이 사용하는 추가 메모리의 함수로 표현된다.
공간 복잡도는 알고리즘의 ‘메모리 효율성’을 측정하는 척도이다.

복잡도 표기법

복잡도를 표현하는 데 주로 사용되는 세 가지 표기법이 있다:

빅오 표기법(Big O Notation) - O(f(n))

알고리즘의 최악의 경우 복잡도를 나타낸다.
즉, 알고리즘이 수행하는 데 필요한 시간 또는 공간의 상한(upper bound)을 표현한다.
가장 널리 사용되는 표기법이다.

예: O(n²)는 알고리즘이 입력 크기 n에 대해 최대 n²에 비례하는 시간이나 공간을 사용한다는 의미이다.

빅오메가 표기법(Big Omega Notation) - Ω(f(n))

알고리즘의 최선의 경우 복잡도를 나타낸다.
즉, 알고리즘이 수행하는 데 필요한 시간 또는 공간의 하한(lower bound)을 표현한다.

예: Ω(n)은 알고리즘이 입력 크기 n에 대해 최소 n에 비례하는 시간이나 공간을 사용한다는 의미이다.

빅세타 표기법(Big Theta Notation) - Θ(f(n))

알고리즘의 평균적인 경우 복잡도를 나타낸다.
상한과 하한이 동일한 경우에 사용된다.

예: Θ(n log n)은 알고리즘이 입력 크기 n에 대해 n log n에 비례하는 시간이나 공간을 사용한다는 의미이다.

주요 시간 복잡도 분류

알고리즘의 시간 복잡도는 다음과 같이 다양한 증가율로 분류된다(낮은 복잡도에서 높은 복잡도 순):

O(1) - 상수 시간(Constant Time)

입력 크기와 관계없이 항상 일정한 시간이 소요된다.

예: 배열에서 인덱스로 직접 원소 접근하기

1
2

def get_element(arr, index):
    return arr[index]  # O(1) 연산

O(log n) - 로그 시간(Logarithmic Time)

입력 크기가 증가할수록, 필요한 시간이 로그 함수처럼 천천히 증가한다.

예: 이진 검색(Binary Search)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # 찾지 못한 경우

O(n) - 선형 시간(Linear Time)

입력 크기에 비례하여 시간이 증가한다.

예: 배열의 모든 원소 순회하기

1
2
3
4
5
6

def find_maximum(arr):
    max_val = float('-inf')
    for num in arr:  # n번 반복
        if num > max_val:
            max_val = num
    return max_val

O(n Log n) - 선형 로그 시간(Linearithmic Time)

많은 효율적인 정렬 알고리즘의 시간 복잡도이다.

예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # n/2 크기 문제
    right = merge_sort(arr[mid:])   # n/2 크기 문제
    return merge(left, right)       # O(n)
    
def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    return result

O(n²) - 이차 시간(Quadratic Time)

입력 크기의 제곱에 비례하여 시간이 증가한다.

예: 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort)

1
2
3
4
5
6
7

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):          # n번 반복
        for j in range(0, n-i-1):  # 최대 n번 반복
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

O(2^n) - 지수 시간(Exponential Time)

입력 크기가 증가함에 따라 시간이 기하급수적으로 증가한다.

예: 피보나치 수열의 재귀적 계산

1
2
3
4

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # 2^n번의 함수 호출

O(n!) - 팩토리얼 시간(Factorial Time)

가장 느린 복잡도 중 하나로, 입력 크기의 팩토리얼에 비례하여 시간이 증가한다.

예: 외판원 문제(Traveling Salesman Problem)를 모든 경로를 확인하여 해결

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def permutations(arr):
    if len(arr) <= 1:
        return [arr]
    
    result = []
    for i in range(len(arr)):
        # 현재 원소를 제외한 나머지 원소들의 순열을 구함
        rest = arr[:i] + arr[i+1:]
        for p in permutations(rest):
            result.append([arr[i]] + p)
            
    return result  # n!개의 순열을 생성

공간 복잡도 예시

O(1) - 상수 공간

입력 크기와 관계없이 일정한 추가 메모리를 사용한다.

예: 두 변수의 값 교환하기

1
2
3
4
5

def swap(a, b):
    temp = a
    a = b
    b = temp
    return a, b

O(n) - 선형 공간

입력 크기에 비례하여 메모리를 사용한다.

예: 배열 복사하기

1
2
3
4
5

def copy_array(arr):
    new_arr = []  # 추가 메모리 O(n)
    for item in arr:
        new_arr.append(item)
    return new_arr

O(n²) - 이차 공간

입력 크기의 제곱에 비례하여 메모리를 사용한다.

예: n×n 행렬 생성하기

1
2
3
4
5
6
7
8

def create_matrix(n):
    matrix = []  # O(n²) 공간
    for i in range(n):
        row = []
        for j in range(n):
            row.append(0)
        matrix.append(row)
    return matrix

복잡도 분석의 규칙

알고리즘 복잡도를 분석할 때 다음 규칙을 적용한다:

1. 상수항 무시
   빅오 표기법에서는 상수항을 무시한다.
   예를 들어, O(2n) = O(n)이다.

2. 낮은 차수 항 무시
   빅오 표기법에서는 낮은 차수의 항을 무시한다.
   예를 들어, O(n² + n) = O(n²)이다.

3. 최대항만 고려
   여러 단계로 구성된 알고리즘의 경우, 가장 높은 복잡도를 가진 단계가 전체 복잡도를 결정한다.

4. 곱셈 법칙
   중첩 루프의 경우, 각 루프의 복잡도를 곱한다.
   예를 들어, O(n) 루프 안에 O(m) 루프가 있다면 전체 복잡도는 O(n×m)이다.

알고리즘 효율성과 트레이드오프

1. 시간과 공간의 트레이드오프
   많은 경우, 시간 효율성과 공간 효율성 사이에는 트레이드오프 관계가 있다.
   더 빠른 알고리즘은 더 많은 메모리를 사용하는 경우가 많다.

   예: 동적 계획법(Dynamic Programming)은 중간 결과를 저장하여 재계산을 피함으로써 시간 복잡도를 줄이지만, 추가 메모리가 필요하다.

   1 2 3 4 5 6 7 8

   # 메모이제이션을 이용한 피보나치 수열 계산 (시간 복잡도: O(n), 공간 복잡도: O(n)) def fibonacci_memoization(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo) return memo[n]

2. 최적화의 원칙
   “조급한 최적화는 모든 악의 근원이다”(Donald Knuth). 실제 상황에서는 코드의 가독성, 유지보수성, 개발 시간 등도 함께 고려해야 한다.

비결정적 알고리즘의 복잡도

1. 평균 복잡도(Average-case Complexity)
   알고리즘이 모든 가능한 입력에 대해 평균적으로 수행하는 시간 또는 공간을 나타낸다.
   확률적 분석이 필요하다.

2. 분할 상환 분석(Amortized Analysis)
   일련의 연산에 대한 평균적인 비용을 분석하는 방법이다.
   단일 연산이 때로는 비용이 많이 들지만, 전체적으로는 효율적인 경우에 사용된다.

   예: 동적 배열에서의 삽입 연산은 대부분 O(1)이지만, 가끔 배열 크기 조정이 필요하여 O(n)이 된다. 분할 상환 분석에서는 이를 O(1)로 표현한다.

병렬 알고리즘의 복잡도

• 작업 복잡도(Work Complexity)
  알고리즘이 수행하는 총 연산의 수로, 순차 실행 시의 시간과 동일한다.
• 깊이 복잡도(Depth Complexity)
  병렬 처리 시 필요한 최소 시간으로, 가장 긴 의존성 경로의 길이를 나타낸다.
• 비용 최적성(Cost Optimality)
  프로세서 수에 대한 작업 복잡도의 비율로, 병렬화의 효율성을 나타낸다.

알고리즘 복잡도와 실제 성능

이론적인 복잡도 분석은 매우 큰 입력 크기에 대한 점근적 성능을 나타낸다.
하지만 실제 성능은 다양한 요소에 의해 영향을 받을 수 있다:

• 하드웨어 성능
  CPU 속도, 캐시 크기, 메모리 계층 구조 등이 실제 성능에 영향을 미친다.
• 언어 및 컴파일러 최적화
  프로그래밍 언어, 컴파일러 최적화, 인터프리터 효율성 등이 실행 시간에 영향을 준다.
• 입력 분포
  알고리즘의 실제 성능은 입력 데이터의 특성에 따라 크게 달라질 수 있다.
  예를 들어, 이미 정렬된 배열에서 삽입 정렬은 O(n)으로 동작한다.
• 상수 인자
  빅오 표기법에서는 무시되는 상수 인자가 실제 성능에는 큰 영향을 미칠 수 있다. 특히 입력 크기가 작을 때는 더욱 그렇다.

실제 분석 예시

정렬 알고리즘 비교

여기서 n은 배열의 크기, k는 배열 내 원소 값의 범위.

자료구조 연산의 복잡도

(*) 표시는 평균적인 경우를 나타내며, 최악의 경우 다를 수 있다.

참고 및 출처