프로그램에서 running time계산할 때
시내
2023.04.01
질문 제목 : 프로그램에서 running time 계산할 때 return은 하나로 안치나요?어짜피 +1은 오더(빅-오)에 영향을 크게못주니 무시해도 되겠지만 궁금하네요
return하는 자체는 하나의 연산으로 안치는 것인가요?질문 내용 :
fib(int n)
{
if(n=1)
return 1;
else
return fib(n-1)+fib(n-2);
}
이런식으로 되어있다면 fib함수의 running time을 t(n)이라고 했을 때 worst case를 고려하여, else문 이하를 보시면t(n)=t(n-1)+t(n-2)+2라고 합니다.
여기에서 +2가 되는 이유가 하나는 조건문 if 안의n=1 비교에 한번 연산이 쓰이고 fib(n-1)+fib(n-2)의 덧셈 연산에 한번 쓰인다고 합니다. 그런데 제 생각에는 계산 후에return을 하니까 t(n)=t(n-1)+t(n-2)+3이 되는 게 맞는 것 아닌가요?
저의 무지함을 일깨워 주십시오~ ㅎㅎ
