Created
September 5, 2018 14:07
-
-
Save fernandoabcampos/c2e55125726fe8d97372b80735d8107c to your computer and use it in GitHub Desktop.
Fibonacci in 3 different approaches.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.time.Duration; | |
| import java.time.Instant; | |
| public class Main { | |
| public static void main(String[] args) { | |
| int n = 30; | |
| //It will take ages to execute if n > 50. E.g.: n = 60 took 63s | |
| printAndMonitorRecursive(n); | |
| // Stackoverflow at some point | |
| printAndMonitorMemoized(n); | |
| // Works in all scenarios | |
| printAndMonitorDynamicProgramming(n); | |
| } | |
| private static void printAndMonitorDynamicProgramming(int n) { | |
| final Instant init = Instant.now(); | |
| System.out.println("F(" + n + "): " + fibonacciDynamicProgramming(n) + "\t took " + Duration.between(init, Instant.now()).toMillis() + " ms - Dynamic Programming"); | |
| } | |
| private static void printAndMonitorMemoized(int n) { | |
| final Instant init = Instant.now(); | |
| System.out.println("F(" + n + "): " + fibonacciMemoized(n) + "\t took " + Duration.between(init, Instant.now()).toMillis() + " ms - Memoized"); | |
| } | |
| private static void printAndMonitorRecursive(int n) { | |
| final Instant init = Instant.now(); | |
| System.out.println("F(" + n + "): " + fibonacciRecursive(n) + "\t took " + Duration.between(init, Instant.now()).toMillis() + " ms - Recursive"); | |
| } | |
| static int fibonacciRecursive(int n) { | |
| if (n == 0 || n == 1) return n; | |
| return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); | |
| } | |
| static int fibonacciMemoized(int n) { | |
| return fibonacciMemoized(n, new int[n + 1]); | |
| } | |
| private static int fibonacciMemoized(int n, int[] memo) { | |
| if (n == 0 || n == 1) return n; | |
| if (memo[n] == 0) { | |
| memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo); | |
| } | |
| return memo[n]; | |
| } | |
| static int fibonacciDynamicProgramming(int n) { | |
| if (n == 0) return 0; | |
| int a = 0; | |
| int b = 1; | |
| for (int i = 2; i < n; i++) { | |
| int c = a + b; | |
| a = b; | |
| b = c; | |
| } | |
| return a + b; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment