본문으로 바로가기

알고리즘의 성능 분석 기법

수행 시간 측정 알고리즘 복잡도 분석
두 개의 알고리즘을 실행하고 수행시간을 측정 직접 구현하지 않고 수행시간을 분석하는것
실제로 구현하는 것이 필요하다 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
동일한 하드웨어를 이용해야 한다 일반적으로 연산의 횟수는 n의 함수

표를 본다면 알 수 있겠지만, 실질적으로 수행시간측정은 효율이 떨어져서 알고리즘 복잡도 분석을 통해서 효율성을 많이 측정 한다.

 

수행시간 측정을 이해하기 위한 코드 구현

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

int main(void){
	clock_t start, stop;
    double duration;
    start = clock(); // 측정시작
    for (int i = 0; i < 100000000000; i++); //이부분을 늘려서 작업량을 늘린다.
    stop = clock(); // 측정종료
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("수행시간은 %f 초 입니다.\n",duration);
    return 0;
}
교수님께서 제시해 주신 for문을 통해 연산을 복잡하게 해서 작업량을 늘리고 줄이고, 결과 시간을 측정하여 프린트해주는 코드
수행 시간 측정을 위해서는 위에 측정할 코드를 직접 구현해서 실행시키고, 시간을 측정해야하는 번거로움이 있다.

복잡도 분석(complexity clac)

시간 복잡도와는 다르게 연산들이 몇번씩 수행되는지 숫자로 표시하는 분석법

ex) a+1 = 연산 1번 if(a+1 = b){.... = 연산 3번

 

복잡도 분석의 종류

  • 시간 복잡도(time complexity)
  • 공간 복잡도(space complexity)

요즘같은 시대엔 메모리가 남아나는 시대인지라, 공간 복잡도 보단 시간 복잡도를 통해서 알고리즘의 효율성을 측정한다.

대표적으로 입력의 개수를 고려한다.(ex 알고리즘 3n+2 , 5n'2 + 3)

 

우리 교수님이 제시해주신 비교 알고리즘과 보기쉽게 정리한 그래프

알고리즘 A,B,C를 비교했을때 단순이 입력하는 수가 늘어난것 뿐인데 A는 전체 연산의 수가 2로 고정되는 반면, C는 기하급수적으로 올라가는 걸 볼수 있다. 아래쪽 전체 연산수를 통해서 복잡도를 알 수 있다.

 


복잡도 표기법

  • 빅오 표기법 <- 제일 많이 사용하는 기법
  • 빅세타 표기법
  • 빅오메가 표기법

빅오 표기법 외의 표기법 설명

더보기

빅 오메가 표기법

 

빅 세타 표기법

 

빅오표기법외에 빅세타, 빅오메가 표기법은 일반적으로 사용되는편이 아니므로 개념적으로만 알면 충분할거 같다.

 

빅오 표기법(Big-O)

최대한 내가 직접 쓰려고 했지만, 쓰려고 하니 너무 머리가 복잡하다.... 교수님이 제시해주신 자료다.

간단히 요약하면 빅오 표기법을 함수의 차수에 큰영향을 받는 표기법이다. 1차수(n) 보다 2차수(n'2)가 더 복잡도에 기여를 한다.

이를 표기하면 O(n), O(n'2)로 표기한다.

 

예시)

마찬가지로 교수님의 예시이다. 머리가 약간 지끈지끈 된다.

예제에 나와있다 시피, 빅오표기는 차수에 영향이 큰것 인걸 알 수 있다.

 

빅오표기법 차수에 따르는 시간 복잡도

빅오 표기법도 상수형, 로그형, 2차,3차 선형로그, 팩토리얼, 지수에 따라 복잡도가 편이하다 이를 이해시키기위한 표와 그래프 이다.

 

이미지에서 볼수 있듯이 상수형은 복잡도가 증가에따라 차이가 없는 반면, 제일 복잡한 팩토리얼형에 경우는 그수가 기하급수적으로 올라가는 복잡도를 볼수 있다.

 

 

빅오 표기법이 일반적인 이유

교수님의 예제 자료

일반적으로 최선의 경우는 복잡도가 무의미한 경우가 많아서 복잡도 분석의 표본으로 삼기 어렵다. 평균적인 경우도 비슷한데 따라서 복잡도를 명확히 판단하기 위해선 최악의 경우를 비교하는것이 계산하기 쉽고 비교확인하기 편하기 때문에 최악의 경우(상한)를 표기하는 빅오 기법을 많이 이용하는것 같다.

 


수업을 들은 느낀점 : 머리가 아프다. 이해를 위해선 나름의 많은 복습이 필요할거 같다. 제일 많이 사용하고 일반적이라는 빅오 기법을 많이 이해하고 복습을 해보아야 할거 같다. 예제에서 알수 있듯이 차수가 낮은건 빅오기법에서는 생략되어서 표기되므로 복잡도 분석의 빅오기법에선 차수가 높은걸 위주로 보아야 겠다.
대가리 아파서 내가 직접 노트한걸 보여주는거 보다 교수님이 인용하신 자료를 쓰는게 맞는거 같아서 이렇게 올려봅니다.
이론 공부 카테고리 설명에서도 그렇듯 내가 공부하는걸 정리해보는 글이기 때문에 정확할 수 없고, 그냥 그런가 보다 하면서 오류는 지적해주시기 바랍니다.
인터넷의 글은 어디까지나 참고만 하지 이것이 진실이라고 믿어선 안된다는 기초를 가지고 제 글을 읽어주셨으면 합니다.