[자료구조] 알고리즘 성능 분석 기법

---

성능 분석 기법

• 수행 시간 측정 - 두 개의 알고리즘의 실제 수행 시간을 측정하고 비교
  • 가정 : 동일한 하드웨어 사용
    
    
• 복잡도 분석
  • 공간 복잡도 : 수행 시 필요로 하는 메모리 공간 분석
  • 시간 복잡도 분석 : 직접 구현하지 않고 수행 시간 분석 ← 수행하는 연산의 횟수를 측정하여 비교

 

---

수행시간 측정 - clock 함수

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(){
    clock_t start,end;
    double duration = 0;

    start = clock(); // clock() 현재 시간을 반환
    // 코드 실행
    // ...
    // 코드 종료
    end = clock();
    duration = (double)(end-start)/CLOCKS_PER_SEC; // 초 단위 환산
    printf("걸린 시간은 %d 입니다 ",duration);
}

 

---

복잡도 분석

• 시간 복잡도
  • 알고리즘이 수행하는 연산의 개수를 계산하여 숫자로 표시
  • 연산의 수행 횟수는 입력의 개수 n에 대한 함수 → 시간복잡도 함수라고 하고 T(n)으로 표기
    
    
• 공간 복잡도
  • 프로그램의 크기 (현재는 크게 신경 안 씀)

 

---

연산 횟수 계산 및 그래프 표현

n을 n번 더하는 문제에서 전체 연산수 구해보기

각 연산의 시간 복잡도

이를 그래프로 나타내면..

그래프로 나타냈을 때

 

---

O(빅오) 표기법

• 연산의 횟수를 점근적으로 표기
• 함수의 상한을 표시
• T(n)=(n2+n+1==n2) T(n)= (n^2+n+1 == n^2) T(n)=(n2+n+1==n2) → 최고차항만 고려해도 충분함
  
  

빅오 정의

• 예) f(n) = 2n + 1, g(n) = n
  • n≥5 일 때 f(n)= 2n+1 < 10*g(n)=10n이므로 f(n) = O(n)
    
    
• 시간 복잡도를 검사할 때 최악의 경우를 가장하여 빅오 표기법을 사용하여 계산한다.

 

---

빅오 표기법 종류

• O(1) : 상수형
• O(logn) : 로그 선형
• O(n) : 선형
• O(nlogn) : 로그 선형
• O(n^2) : 2 차형
• O(n^3) : 3 차형
• O(n^k) : k차형
• O(2^n) : 지수형
• O(n!) : 팩토리얼형

 

---

그 외 표기법

• 빅오메가 표기법 : 함수의 하한을 표시

• 빅세타 표기법 : 함수의 하한과 상한을 동시에 표시