알고리즘의 분석

알고리즘의 분석

---

알고리즘의 분석이란 알고리즘의 성능을 평가하는 과정입니다. 설계된 알고리즘이 얼마나 효율적으로 주어진 문제를 해결하는지 알고리즘의 효율성을 정량적으로 측정하고 비교하기위해 수행됩니다. 분석은 주로 시간과 공간의 관점에서 이루어지며 이를 통해 더 나은 알고리즘을 설계하거나 최적의 알고리즘을 선택할 수 있습니다.

 

알고리즘 분석의 목적

1. 효율성 평가 : 주어진 입력에서 알고리즘이 얼마나 빠르고 효율적으로 실행되는지 평가 하기 위해서 입니다.
2. 비교 및 선택 : 여러 알고리즘 중에서 적절한 알고리즘을 선택하기 위해서 입니다.
3. 자원 관리 : 제한된 시간과 메모리 용량을 효율적으로 사용하는 알고르즘을 설계 하기 위해서 입니다.

 

알고리즘 분석의 기준

시간 복잡도(Time Complexity) 분석

시간 복잡도는 알고리즘이 실행되는데 걸리는 시간을 입력크기 n에 대한 함수로 표현한 것입니다.

 

실제로 측정하기에는 CPU의 성능, 프로그래머가 작성하는 방식 등에 따라서 알고리즘이 실행되는데 걸리는 시간이 달라지기 때문에 연산 횟수의 증가 패턴을 분석하여 효율성을 평가합니다.

 

시간 복잡도 표현 방법

 

시간 복잡도는 빅오 표기법(Big-O Notation)으로 나타내며 가장 빠르게 증가하는 항을 기준으로 표현합니다.

• 입력 크기 nnn이 커질 때 알고리즘의 실행 시간이 어떻게 변하는지 나타냅니다.
• 주로 사용하는 표현:
  • O(1) : 상수 시간
  • O(log⁡n) : 로그 시간
  • O(n) : 선형 시간
  • O(n^2) : 이차 시간
  • O(2^n) : 지수 시간

시간 복잡도 분석 과정

1. 입력 크기 결정 : 입력 크기 n은 데이터의 크기로 피보나치 수열에서 F(5) 같이 n 에 숫자가 들어가는데 해당 n은 입력이고 입력크기는 아닙니다. 입력크기는 n을 부호화(Encode)한 기호(symbol)의 개수로 잡습니다. 예를 들면 n = 5일 때 101 즉 3비트이고 n = 13일 경우 1101 즉 4비트만큼의 자리를 차지합니다.
2. 단위연산(Basic Instruction) : 단위연산을 선정하여 알고리즘이 실행한 총 작업의 양을 실행한 횟수에 대략적으로 비례하도록 합니다.
3. 반복문의 영향 분석 : 반복문, 중첩 반복문의 횟수를 계싼하여 실행 횟수를 추정합니다.
4. 빅오 표기법으로 단순화 : 가장 빠르게 증가하는 항만 남기고 나머지는 무시합니다.

 

공간 복잡도(Space Complexity) 분석

공간 복잡도는 알고리즘이 실행될 때 사용하는 메모리 양을 입력 크기 n에 대한 함수로 분석한 것입니다. 실행 중 사용하는 메모리 자원의 양을 측정합니다.

 

공간 복잡도를 구성하는 요소

공간 복잡도는 고정 공간과 가변 공간으로 나눌 수 있습니다.

• 고정 공간(Fixed Space) : 알고리즘이 입력 크기와 무관하게 항상 사용하는 메모리 공간으로 빅오 표기법으로는 O(1)입니다.
• 가변 공간(Variable Space) : 입력 크기에 따라서 변하는 메모리 공간으로 빅오 표기법은 알고리즘마다 달라 예를 들면 O(n), O(logn) 등이 있습니다.

공간 복잡도 분석 과정

1. 입력 공간 계산 : 입력 데이터 크기가 얼마인지 계산합니다.
2. 알고리즘에서 사용하는 추가 메모리 분석 : 변수, 배열 등을 포함하여 사용되는 메모리 공간을 계산합니다.
3. 전체 메모리 사용량 합산 : 입력 공간과 추가 메모리 사용량을 더해 공간 복잡도를 분석합니다.