알고리즘 복잡도 (시간 복잡도)

알고리즘 성능 ? 시간이 덜 걸리고 메모리를 덜 사용하는 알고리즘이 좋은 것

 

입력되는 data의 개수 n 에 대해서 걸리는 시간과 공간을 수식화 한 것

 

이를 통해 알고리즘을 쉽게 비교할 수 있음

 

ex) A1  n-> n^2

     A2  n-> 2^n

  A1이 A2보다 시간적으로 빠르다. 더 좋다고 말할 수 있다.

 

 

<Big-O notation>

2*n^2 이나 3n^2이나 O(n^2) 이다. n이 굉장히 커졌을 때 무시해도 되는 경우는 생략한다.

따라서 둘은 비슷한 성능을 가졌다고 볼 수 있다.

n^2+n+1 => O(n^2)

3*2^n => O(2^n)

 

O(1) 

 : n의 갯수에 상관이 없이 항상 같음. 꿈의 알고리즘

O(n)

O(n*logn)

O(n^2)

O(2^n)

O(n!)

 

아래로 갈수록 안좋은 알고리즘

 

c언어 코드 수행시간 측정하는 방법

//수행시간 측정

#include <stdio.h>

#include <time.h>  //clock() 이 함수를 호출할때의 clock cnt

                          //Start와 End를 통해 시간을 알 수 있음 

void main()

{

    clock_t start_time, end_time; //int, char

    start_time = clock();

    //WORK

    end_time = clock();

    print(%d \n", end_time-start_time);

}



//duration --clock cnt

//duration / CLOCKS_PER_SEC --> 초