Algorithm Complexity (Big-O)

0. 서론 : 알고리즘 복잡도의 중요성

프로그래밍에서 중요한 과제 중 하나는, 동일한 기능을 수행하는 여러 가지 코드 중에서 가장 효율적인 코드를 선택하는 것입니다.

• 하지만 어떤 코드가 더 효율적인지 평가하기 위해서는 단순히 실행 속도만 보는 것이 아니라, 그 코드가 입력 크기가 커질수록 얼마나 더 많은 시간과 메모리를 사용하는지 분석하는 것이 필요합니다.

이때 사용하는 개념이 바로 알고리즘 복잡도입니다.

• 알고리즘 복잡도는 코드의 성능을 측정하는 도구로, 주로 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉩니다.
• 이를 통해 코드가 처리할 데이터가 많아질수록 얼마나 더 많은 시간이 걸리고, 얼마나 더 많은 메모리를 사용하는지를 수학적으로 예측할 수 있습니다.

현대 컴퓨팅 환경에서는 처리해야 할 데이터가 수십만, 수백만 개에 이르는 경우도 흔합니다.

• 이럴 때, 비효율적인 알고리즘은 막대한 자원을 소모하게 되어 프로그램이 실제로 작동하지 않거나, 매우 느리게 실행되는 문제가 발생할 수 있습니다.
• 따라서 알고리즘 복잡도를 이해하고 적절한 알고리즘을 선택하는 것이 필수적입니다.

본 포스팅에서는 알고리즘 복잡도를 이해하기 위한 Big-O 표기법을 중심으로, 시간 복잡도와 공간 복잡도 개념을 다루고, 이를 통해 효율적인 코드를 작성하는 방법을 소개하겠습니다.

1. 시간 복잡도 (Time Complexity)

1.1 시간 복잡도란?

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기에 따라 수학적으로 나타낸 것입니다.

• 즉, 입력 데이터의 크기가 커질수록 알고리즘이 얼마나 더 많은 시간이 걸리는지를 측정하는 척도라고 할 수 있습니다.

알고리즘 성능을 평가할 때 중요한 것은 입력 크기가 증가할 때 시간의 증가율입니다.

• 이러한 시간 복잡도는 주로 Big-O 표기법으로 표현됩니다.

1.2 Big-O 표기법 (on the order of)

Big-O 표기법은 입력 크기 n이 커질수록 알고리즘이 수행하는 연산 횟수의 상한을 표현합니다.

• 이때, Big-O 표기법에서는 상수와 저차항이 무시됩니다.
• 즉, 연산 시간이 O(2n)이나 O(3n+5)처럼 표현될 수 있지만, Big-O 표기법에서는 주된 증가 요인만 남기고 상수는 생략하여 O(n)으로 단순화됩니다.

예시:

• O(2n) → O(n)
• O(3n^2 + 5n + 10) → O(n^2)

이렇게 표기하는 이유는 입력 크기가 매우 커질 때 상수 항이 성능에 미치는 영향이 미미하기 때문입니다.

• 따라서 알고리즘 분석 시에는 상수보다는 시간 증가의 패턴을 더 중요하게 봅니다.

1.3 시간 복잡도 예시

• 위 이미지를 보면, 서로 다른 시간 복잡도를 가진 알고리즘이 입력 크기 n에 따라 어떻게 성능이 변하는지를 한눈에 알 수 있습니다.

그럼 대표적으로 많이 쓰이는 7가지 정도의 시간복잡도를 정리해보겠습니다.

• O(1): 상수 시간 복잡도

  • 데이터의 크기와 무관하게 동일한 시간이 소요되는 알고리즘입니다.
  • 예시: 배열의 첫 번째 값을 조회하는 연산.

• O(log n): 로그 시간 복잡도

  • 입력 크기가 커질수록 증가하는 속도가 느려지는 알고리즘입니다.
    • 이진 탐색(binary search)처럼 데이터의 절반을 한 번에 버릴 수 있는 경우에 주로 발생합니다. (참고로 log의 밑도 상수로 취급해서 일반화합니다)
  • 예시: 정렬된 배열에서 값을 찾는 이진 탐색.

• O(n): 선형 시간 복잡도

  • 입력 크기에 비례해 시간이 증가하는 알고리즘입니다.
    • 데이터를 한 번씩 모두 확인해야 하는 경우 주로 발생합니다.
  • 예시: 배열의 모든 값을 순차적으로 확인하는 선형 탐색(linear search).

• O(n log n): 로그 선형 시간 복잡도

  • 빠른 정렬 알고리즘, 예를 들어 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)에서 나타납니다.
    • 데이터 크기가 커질 때 상대적으로 효율적입니다.
  • 예시: 퀵 정렬, 병합 정렬.

• O(n^2): 이차 시간 복잡도

  • 이중 반복문처럼, 모든 요소를 두 번씩 확인해야 할 때 발생하는 시간 복잡도입니다.
  • 예시: 버블 정렬(Bubble Sort)과 같은 단순한 정렬 알고리즘.

• O(2^n): 지수 시간 복잡도

  • 입력이 하나 증가할 때마다 실행 시간이 두 배로 증가하는 알고리즘입니다.
    • 보통 재귀적인 문제나 백트래킹 문제에서 나타납니다.
  • 예시: 피보나치 수열을 계산하는 단순 재귀 알고리즘.

• O(n!): 팩토리얼 시간 복잡도

  • 매우 비효율적인 시간 복잡도로, 데이터의 모든 가능한 순열을 확인해야 하는 경우 발생합니다.
  • 예시: 순열을 전부 확인하는 완전 탐색 알고리즘.
    
    
    

이와 같이 시간 복잡도는 알고리즘의 성능을 측정하고 비교하는 매우 중요한 지표입니다.

• 알고리즘을 설계하거나 선택할 때 이러한 시간 복잡도를 고려해야만 효율적인 프로그램을 만들 수 있습니다.

3. 공간 복잡도 (Space Complexity)

3.1 공간 복잡도란?

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리의 양을 측정하는 척도입니다.

• 알고리즘이 문제를 해결하는 데 얼마나 많은 메모리를 필요로 하는지 입력 크기 n에 따라 분석합니다.

공간 복잡도는 알고리즘이 메모리를 얼마나 효율적으로 사용하는지를 평가하는 중요한 지표입니다.

• 특히, 제한된 메모리 환경에서는 공간 복잡도를 고려한 알고리즘 설계가 필수적입니다.

다만, 기술이 발전함에 따라 고용량 메모리 가격은 상당히 낮아졌기 때문에, 시간복잡도에 비해선 상대적으로는 중요도가 떨어지는 것이 사실입니다.

• 그럼에도 지나치게 많은 메모리를 잡아먹는 알고리즘은 효율적인 알고리즘이라 할 수 없기 때문에 공간 복잡도 또한 중요하게 고려해야합니다.

3.2 Big-O 표기법과 공간 복잡도

공간 복잡도도 시간 복잡도와 마찬가지로 Big-O 표기법으로 표현됩니다.

이때, 공간 복잡도는 알고리즘 실행 중에 필요한 고정 메모리(상수 크기)와 입력 크기에 따라 변하는 메모리로 나눌 수 있습니다.

• O(1): 상수 공간 복잡도
  • 알고리즘이 추가적인 메모리를 거의 사용하지 않는 경우.
  • 예시: 입력 크기와 상관없이 몇 개의 변수를 사용하는 경우 (ex. 값 교환 알고리즘).
• O(n): 선형 공간 복잡도
  • 알고리즘이 입력 크기 n에 비례해서 메모리를 사용하는 경우.
  • 예시: 새로운 배열을 생성하거나 리스트에 데이터를 저장하는 경우.
• O(n^2): 이차 공간 복잡도
  • 이중 배열이나 이중 리스트 등, 데이터 구조가 이차원적으로 증가할 때 발생.
  • 예시: 2차원 배열을 사용하는 행렬 연산.

3.3 공간 복잡도의 분석 방법

공간 복잡도를 분석할 때는 주로 두 가지 메모리 요소를 고려합니다:

1. 고정 공간 (Fixed Space): 알고리즘 실행에 필요한 고정된 메모리, 즉 입력 크기와 관계없이 상수 크기의 메모리를 사용하는 변수, 상수 등을 포함합니다.
2. 가변 공간 (Variable Space): 입력 크기 n에 따라 가변적으로 증가하는 메모리.
   예를 들어 배열, 리스트, 재귀 호출에서 추가적으로 사용하는 메모리 등이 해당됩니다.

예시 ( java )

int sum(int[] arr) {
    int total = 0;  // 고정 공간 (상수 크기)
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];  // 가변 공간 (배열의 크기에 비례)
    }
    return total;
}

위 코드에서 total 변수는 O(1)의 고정 공간을 차지하지만, 배열 arr는 입력 크기 n에 비례한 O(n)의 메모리를 사용합니다.

4. 시간 복잡도와 공간 복잡도의 균형

알고리즘을 최적화할 때는 시간 복잡도와 공간 복잡도 사이의 균형이 중요합니다.

• 때로는 더 많은 메모리를 사용해서 시간을 절약하거나, 반대로 시간이 더 걸리더라도 메모리를 절약할 수 있습니다.
• 이러한 균형은 주로 동적 프로그래밍(Dynamic Programming)에서 자주 고려됩니다.

예시:

• 메모이제이션(Memoization): 중복 계산을 피하기 위해 메모리를 더 사용하여 시간을 절약하는 방식.
  • 예를 들어, 피보나치 수열을 동적 프로그래밍으로 풀 때는 중간 결과를 저장해 O(n)의 시간 복잡도를 달성하지만, 저장 공간이 O(n)으로 증가합니다.

5. 결론 : 복잡도 분석의 실제적 응용

알고리즘의 시간 복잡도와 공간 복잡도를 분석하는 것은 이론적으로도 중요하지만, 실제 개발 환경에서 성능을 최적화하는 데에 핵심적인 역할을 합니다.

• 특히 대규모 데이터를 다루거나 복잡한 연산을 반복적으로 수행해야 하는 경우, 효율적인 알고리즘을 선택하는 것이 프로그램의 성능을 크게 좌우할 수 있습니다.

5.1 실제 개발에서 복잡도 고려

실제 개발 환경에서는 다음과 같은 상황에서 알고리즘 복잡도 분석이 중요한 역할을 합니다:

• 대용량 데이터 처리
  • 빅데이터 분석, 데이터베이스 처리, 로그 파일 분석 등의 경우, 처리할 데이터가 수백만에서 수십억 개에 이를 수 있습니다.
  • 이럴 때, 비효율적인 알고리즘을 선택하면 처리 시간이 기하급수적으로 늘어나기 때문에, 시간 복잡도에 대한 철저한 분석이 필요합니다.
• 실시간 시스템
  • 금융 거래 시스템, 게임 서버, IoT 시스템 등 실시간으로 데이터를 처리해야 하는 경우, 알고리즘이 일정 시간 내에 결과를 반환하지 못하면 시스템 전체의 성능에 악영향을 미칠 수 있습니다.
  • 이때 상수 시간이나 로그 시간 복잡도를 가지는 알고리즘을 사용하는 것이 중요합니다.
• 제한된 메모리 환경
  • 모바일 기기, 임베디드 시스템 등 메모리가 제한된 환경에서는 메모리 사용을 최소화하는 것이 필수입니다.
  • 공간 복잡도를 낮추는 알고리즘을 선택해 효율적으로 메모리를 사용하는 것이 중요합니다.

5.2 복잡도 분석의 실제 사례

• 빅데이터 분석
  • MapReduce 같은 대용량 데이터 처리 프레임워크에서는 알고리즘의 시간 복잡도를 최적화하여 분산 환경에서 데이터를 빠르게 처리할 수 있습니다.
  • 이 과정에서 데이터의 크기에 비해 시간이 어떻게 변하는지 예측할 수 있는 복잡도 분석이 핵심입니다.
• 머신러닝
  • 머신러닝 알고리즘은 학습 데이터의 크기에 따라 성능이 크게 달라집니다.
  • 예를 들어, K-최근접 이웃(K-NN) 알고리즘은 시간 복잡도가 O(n)으로 매우 비효율적일 수 있지만, KD-트리나 볼로노이 다이어그램, 등을 사용해 성능을 개선할 수 있습니다.
• 웹 서버 최적화
  • 웹 서버에서 트래픽이 많아질 때, 각 요청에 대해 데이터베이스 조회, 파일 처리 등을 수행하는 알고리즘이 시간이 오래 걸리면 응답 속도가 느려집니다.
  • 따라서 캐싱, 메모이제이션 등의 기법을 활용하여 시간과 공간 복잡도를 최적화해야 합니다.

5.3 알고리즘 최적화 Tip

복잡도 분석을 통해 알고리즘을 최적화할 때는 필요한 수준의 성능과 자원 사용을 고려하여 균형을 맞추는 것이 중요합니다.

• 때로는 공간을 절약하고, 때로는 시간을 절약하는 등 적절한 선택을 통해 최적의 성능을 이끌어낼 수 있습니다.

마무리

알고리즘 복잡도는 프로그램 성능을 결정짓는 중요한 요소입니다.

• 특히 대규모 데이터 처리나 실시간 시스템과 같은 환경에서는 비효율적인 알고리즘이 치명적인 성능 문제를 야기할 수 있습니다.
• 따라서 시간 복잡도와 공간 복잡도를 잘 이해하고, 이를 통해 적절한 알고리즘을 선택하는 것이 효율적인 프로그램을 만드는 핵심입니다.

이 글을 통해 Big-O 표기법을 중심으로 시간 복잡도와 공간 복잡도의 개념을 이해하고, 실제 개발 환경에서 이를 어떻게 적용할 수 있는지 살펴보았습니다.

이후의 포스팅부터는 알고리즘들을 다루기 이전에 대부분의 알고리즘에 기반이 되는 다양한 자료구조들에 대해서 코드와 함께 정리해볼 것입니다.

• 프로그래밍 언어는 Python과 Java중에서 고민중이긴한데, Python은 기본적으로 편의성을 개선한 자료구조들을 활용하고 있어서 주로 Java를 통해 실습을 진행해보고자합니다.