프로그래밍에서 시간 복잡도,GetTickCount()(C++)

시간 복잡도란, 문제를 해결하는데 걸리는 시간을 주어진 데이터 N에 비례해서 양적으로 표현하는 방법이다.

for( i = 0; i < n;i++); 

위와 같은 for나 while 같은 순환문이 한번 돌게 되면 N번이 돌개되는 것이다.

그리고 이중 삼중의 for문은 총 순환 횟수가 N² N³ 가 된다.

보통 50,000,000개의 루틴을 처리하는데 1초정도 걸린다.



그럼 프로그램에서 데이터를 처리하는데 걸린 시간을 구체적으로 구해보자


<windows.h>에서 제공하는 GetTickCount()는 시스템이 시작된 이후에 경과된 시간을 1/1000초 단위로 알려준다.



#include <iostream>
#include <windows.h>//GetTickCount()를 사용하려면 반드시 써주자

using namespace std;
int main(){
   
    int n,i,j,a,t;
    
    cin >> n;
   
    t=GetTickCount();
   
    for(i=0; i<n;i++)for(j=0;j<n;j++)a=i+j;
   
    cout << (GetTickCount()-t)/1000. <<endl;//.을 붙혀서 float으 캐스팅한다.
       
    system("PAUSE");
   
    return 0;
}

다음과 같은 프로그램을 짠뒤 n에 10000을 대입해 보았다. 총 1억번 순환하게 되므로 이론상 2초가 걸려야 한다.


10000
0.297
Press any key to continue . . .
내 컴이 너무 좋은걸까?? 50,000,000 번 순환하는데 1초가 걸린다는 말은 이젠 너무 오래되서 더이상 맞지 않나보다. 1억번이 0.29초니까. 350,000,000 정도가 1초 걸릴 것이다.

그래서,

한번 19000을 대입해 봤다. 19000을 제곱하면 361,000,000이므로 얼추 비슷하다.


19000
1.093
Press any key to continue . . .