Class Fibonacci

java.lang.Object
topics.dynamic.Fibonacci
public class Fibonacci extends Object
DYNAMIC PROGRAMMING: CALCULATE THE FIBONACCI NUMBER OF ORDER n Fibonacci Series = 0,1,1,2,3,5,8,13,21,34,55,89,... e.g. the 0 is when n=0 and the 89 is when n=11
Author:
vicegd

  • Constructor Summary

    Constructors
    Constructor
    Description
    Fibonacci()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    fib1(int n)
    First iterative solution with a temporal complexity O(n)
    int
    fib2(int n, int[] v)
    Second iterative solution with time complexity O(n) and that uses a vector.
    int
    fib3(int n)
    First recursive version, with a linear complexity O(n).
    int
    fib4(int n)
    Second recursive version, with equation T(n)=T(n-1)+T(n-2)+O(1), that once solved is exponential O(1.6^n).
    int
    fib5(int n)
    DandC sophisticated solution that is O(log n).

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Fibonacci

      public Fibonacci()

  • Method Details

    • fib1

      public int fib1(int n)
      First iterative solution with a temporal complexity O(n)
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n

    • fib2

      public int fib2(int n, int[] v)
      Second iterative solution with time complexity O(n) and that uses a vector. Simple case of the DYNAMIC PROGRAMMING technique (MORE ON THAT LATER IN THE COURSE)
      Parameters:
      n - Positive number to be used as input
      v - Array to help in the calculation
      Returns:
      Fibonacci value for n

    • fib3

      public int fib3(int n)
      First recursive version, with a linear complexity O(n). It is DandC by subtraction with a=1,b=1,k=0 - O(n)
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n

    • fib4

      public int fib4(int n)
      Second recursive version, with equation T(n)=T(n-1)+T(n-2)+O(1), that once solved is exponential O(1.6^n). IN SHORT, THIS IS AN UNAFFORDABLE SOLUTION
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n

    • fib5

      public int fib5(int n)
      DandC sophisticated solution that is O(log n). It is DandV by division with a=1,b=2,k=0 and it is programmed in an iterative way.
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n