من برنامه ی سری فیبوناچی را به دو صورت بازگشتی و ساده نوشتم.
از راه بازگشتی برای عدد 50 حدود 3 دقیقه و ۳۹ ثانیه طول کشید
از راه غیربازگشتی برای عدد 50 کمتر از یک میلی ثانیه طول کشید.
میخواستم ببینم علت چیست؟ و چگونه میتوانم تابع زمانی مربوط به الگوریتم های بازگشتی و غیربازشتی این مسئله را بدست آورم؟
import java.util.Calendar;
/**
*
* @author milad
*/
public class Recursive {
public static long recursiveFibonacci( long n ) {
if ( n == 0 || n == 1 ) {
return n;
} else {
return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
}
}
public static long fibonacci( long n ) {
if ( n == 0 ) {
return 0;
}
if ( n == 1) {
return 1;
}
long a = 0;
long b = 1;
long c;
while ( n > 1 ) {
c = a + b;
a = b;
b = c;
n--;
}
return b;
}
public static void main(String[] args) {
System.out.println(System.currentTimeMillis());
System.out.println(fact.recursiveFactorial(5));
System.out.println(System.currentTimeMillis());
System.out.println(fibonacci(50));
System.out.println(System.currentTimeMillis());
}
}