Generating Fibonacci number in java
This article goes through different implementations of Fibonacci numbers in java.
Brute Force: Recursive
The following code is recursive implementation with time complexity O(2**N). That is time complexity is equal to 2 power N.
public int fib(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}Topdown Implementation
Top-down implementation with time complexity of O(N). Here we cache the value at a specific stage and then see if the stage is already calculated, then return from the cache.
public static int fib_topdown(int n, int td[]) {
if (td[n] != 0 && n != 0)
return td[n];
else if (n == 0)
td[n] = 0;
else if (n == 1)
td[n] = 1;
else
td[n] = fib_topdown(n - 1, td) + fib_topdown(n - 2, td);
return td[n];
}
Bottom-Up approach
The code is self-explanatory we use the fundamentals of Fibonacci.
public static int fib_bottomup(int n) {
if (n < 2)
return n;
int f0 = 0;
int f1 = 1;
int f2 = 0;
for (int i = 2; i <= n; i++) {
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f2;
}
No comments :
Post a Comment
Please leave your message queries or suggetions.
Note: Only a member of this blog may post a comment.