알고리즘 성능 : 시간복잡도와 공간복잡도 (Big-O)

알고리즘 성능을 판단하는 복잡도

알고리즘 성능을 판단하는 주요 수단은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)입니다. 이 두 가지는 알고리즘이 실행되는 데 필요한 자원(시간과 메모리)을 평가하는 중요한 기준입니다. 자세히 살펴보면:

 

1. 시간 복잡도 (Time Complexity)

• 정의 : 주어진 입력 크기 nn에 대해 알고리즘이 실행되는 데 걸리는 시간의 양을 측정합니다.
• 목적 : 입력 크기가 커질수록 알고리즘이 얼마나 빨리 실행되는지를 평가합니다.
• 표기법 : 보통 빅오 표기법 (Big O Notation)을 사용하여 최악의 경우를 나타냅니다. 예를 들어 :
  • O(1)O(1) : 상수 시간 복잡도
  • O(n)O(n) : 선형 시간 복잡도
  • O(n2)O(n^2) : 이차 시간 복잡도
  • O(log⁡n)O(\log n) : 로그 시간 복잡도
  • O(nlog⁡n)O(n \log n) : 로그 선형 시간 복잡도

2. 공간 복잡도 (Space Complexity)

• 정의 : 알고리즘이 실행되는 동안 사용하는 메모리의 양을 측정합니다.
• 목적 : 입력 크기가 커짐에 따라 알고리즘이 얼마나 많은 메모리를 사용하는지를 평가합니다.
• 표기법 : 시간 복잡도와 마찬가지로 빅오 표기법을 사용하여 표현합니다. 예를 들어:
  • O(1)O(1) : 상수 공간 복잡도
  • O(n)O(n) : 선형 공간 복잡도
  • O(n2)O(n^2) : 이차 공간 복잡도

3. 최악의 경우 (Worst-case)와 평균 경우 (Average-case) 분석

• 최악의 경우: 알고리즘이 가장 비효율적으로 실행될 때의 시간 또는 공간 복잡도를 분석합니다. 일반적으로 알고리즘의 성능을 판단할 때 최악의 경우를 기준으로 평가합니다.
• 평균 경우: 다양한 입력에 대해 알고리즘이 평균적으로 어떻게 동작하는지 분석합니다. 평균적인 성능을 평가하는 데 사용됩니다.

4. 실행 시간 (실제 성능 측정)

• 실험적 분석 : 이론적 분석 외에도 실제 환경에서 알고리즘을 실행하여 소요되는 시간을 측정하는 방법입니다. 특히 입력 크기나 조건에 따라 이론적 분석이 아닌 실제 성능이 중요한 경우가 있습니다.

5. 다른 평가 기준들

• 안정성 (Stability) : 알고리즘이 주어진 입력에서 동작할 때 결과의 일관성을 유지하는지 여부.
• 간결성 (Simplicity) : 알고리즘이 얼마나 직관적이고 구현하기 쉬운지.
• 확장성 (Scalability) : 입력 크기가 커졌을 때 알고리즘이 잘 동작할 수 있는지.
• 병렬성 (Parallelism) : 알고리즘이 병렬 처리에 적합한지 여부.

예시 :

• 버블 정렬 : 시간 복잡도는 O(n2)O(n^2), 공간 복잡도는 O(1)O(1)입니다.
• 병합 정렬 : 시간 복잡도는 O(nlog⁡n)O(n \log n), 공간 복잡도는 O(n)O(n)입니다.

결국, 알고리즘의 성능을 평가하는 것은 시간과 공간뿐만 아니라 여러 다른 측면에서 이루어집니다. 성능을 최적화하려면 여러 측면에서 균형을 잘 맞추는 것이 중요합니다.