수다닷컴

질문 제목 :
피보나치수열, n팩토리얼 시간복잡도를 점근표기법으로 나타내기

복잡도 내용이해가 힘드네요..
피보나치 수열과 팩토리얼의 복잡도
반복문과 순환문의 차이점을 알고싶습니다..
질문 내용 :

먼저 피보나치수열입니다..

#include stdio.h
#include windows.h
long hamsu(int n); /*long hamsu(int)*/
int main(void)
{
LARGE_INTEGER freq, startTime, endTime;
int n, i; /*변수선언*/
int sum=0;printf(반복하고자 하는 숫자 입력);
scanf(%d,&n);
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&startTime);
for(i = 0 ; i = n ; i ++) /*반복문사용*/
{
sum+=i ;
}QueryPerformanceCounter(&endTime);
printf(n 피보나치 결과는 %d\n,sum);

printf(Run Time : %.12f \n, (double)(endTime.QuadPart - startTime.QuadPart)/freq.QuadPart);; /* 시간출력*/

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&startTime);
sum=hamsu(n); /*함수호출*/

QueryPerformanceCounter(&endTime);
printf(n개의 피보나치 결과는 %d\n,sum);

printf(Run Time : %.12f \n, (double)(endTime.QuadPart - startTime.QuadPart)/freq.QuadPart);; /* 시간출력*/
system(pause);

return 0;
}
long hamsu(int n){
int i;
int sum=0;
for(i=0;i=n;i++)
{
sum+=i;
}
return sum;
}

----------------------------------------------------다음은 팩토리얼 ---------------------------------------

반복문
#include stdio.h
#include windows.h
long hamsu(int n);
int main(void)
{
LARGE_INTEGER freq, startTime, endTime;
int n, i; /*변수선언*/
int mult=1;

printf(숫자 입력);
scanf(%d,&n);
QueryPerformanceFrequency(&freq); /*시간측정*/
QueryPerformanceCounter(&startTime);
for(i = 1 ; i = n ; i ++) /*반복문*/
{
mult*=i ;
}

QueryPerformanceCounter(&endTime); /*시간 측정*/
printf(반복문 n! 결과는 %d\n,mult);

printf(Run Time : %.12f \n, (double)(endTime.QuadPart - startTime.QuadPart)/freq.QuadPart);; /* 시간출력*/

QueryPerformanceFrequency(&freq); /*시간측정*/
QueryPerformanceCounter(&startTime);
mult=hamsu(n); /*함수호출*/QueryPerformanceCounter(&endTime); /*시간측정*/
printf(순환문 n! 결과는 %d\n,mult);

printf(Run Time : %.12f \n, (double)(endTime.QuadPart - startTime.QuadPart)/freq.QuadPart);; /* 시간출력*/

return 0;
}
long hamsu(int n){
int i;
int mult=1;

for(i=1;i=n;i++)
{
mult*=i;
}
return mult;

}

피보나치나 팩토리얼이나 둘다 반복문과 함수호출을 사용해서 나오는 복잡도는
for문으로 n번씩 돌아가니
점근표기법으로 O(n) 이 되는것인가요? 자세히 좀 부탁드릴게요 ㅠ

반복문과 하나는 함수를 이용해서 한것인데 함수호출로 짠 소스는 순환문이 맞나요?
반복문과 순환문의 차이점을 알고 싶습니다.

신청하기