Write function to compute Nth fibonacci number

[GingerBear]

尽可能不用IDE写出所有方法，然后分析一下。

[dianadujing]

只知道recursive和iterative两种。。。

[GingerBear]

最基础的动态规划题，动规的思想是把中间结果保存起来（缓存），留着以后用，从而大大减少不必要的重复计算。

Recursion DP

递归做法比较直观地使用了动规，用一个整型数组保存每次计算的结果，如果在某次递归中发现曾经计算过，立即返回保存着数组中的结果。同时利用了数组的引用传值，保证在层层递归中，只有一个公用的缓存。

时间复杂度为O(n)，还不知如何分析是好。 空间复杂度O(n)，因为额外使用了用来保存结果的数组，数组长度就是n。同时递归的深度最深为n，所以空间同样是n。

static int fib_rec(int i) {
    if (i <= 2) return 1;
    int[] memo = new int[i];
    memo[0] = 1;
    memo[1] = 1;
    for (int j = 2; j < i; j++) {
        memo[j] = 0;
    }
    return fib_rec_helper(i, memo);
}

static int fib_rec_helper(int i, int memo[]) {
    if (memo[i-1] == 0) {
        memo[i-1] = fib_rec_helper(i - 1, memo) + fib_rec_helper(i - 2, memo);
        return memo[i-1];
    } else {
        return memo[i-1];
    } 
}

Iteration DP

迭代做法（或者叫递推比较好）比较符合正常思维，就是只记录最新的两个值，一个一个往前算。个人觉得这不能严格算动态规划，尽管有人觉得算。 时间复杂度O(n)，因为循环了n次。 空间复杂度O(1)，因为不管n多大，只是用常数个变量。

static int fib2(int i) {
    if (i <= 2) return 1;
    int i1 = 1, i2 = 1, tmp = 0;

    for (int j = 2; j < i; j++) {
        tmp = i1;
        i1 = i2;
        i2 = tmp + i2;
    }
    return i2;
}

Test Case

public static void main(String [] args) {
    simpleAssert(fib_rec(1) == 1, "fib_rec: 1");
    simpleAssert(fib_rec(3) == 2, "fib_rec: 3");
    simpleAssert(fib_rec(7) == 13, "fib_rec: 7");
    simpleAssert(fib_rec(19) == 4181, "fib_rec: 3");

    simpleAssert(fib2(1) == 1, "fib2: 1");
    simpleAssert(fib2(3) == 2, "fib2: 3");
    simpleAssert(fib2(7) == 13, "fib2: 7");
    simpleAssert(fib2(19) == 4181, "fib2: 3");
}

static void simpleAssert(Boolean ifSuccess, String msg){
    if (ifSuccess) {
        System.out.println("SUCCESS:\t" + msg);
    }else{
        System.out.println("FAILS:\t" + msg);
    }
}

[GingerBear]

@dianadujing 其实还有一个矩阵的作法，但没什么意思，主要是希望能从这题里总结一下递归和动态规划的基础的东西。

[dianadujing]

Recursive way:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class FibonacciR {
    public static int fibonacciN(int input){
        if(input == 0)
            return 0;
        else if(input == 1)
            return 1;
        return fibonacciN(input-1)+fibonacciN(input-2);
    }
    public static void main(String[] args){
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int x=0;
        System.out.println("Input an integer: ");
        try {
            x=Integer.parseInt(in.readLine());
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("The result of Fibonacci is: "+fibonacciN(x));

    }
}

Time Complexity: O(2^n) because nth sequence needs two recursive sequence--(n-1) and (n-2). On CC150, there is a better solution by using cache--Caching results between calls. The modified version of Fibonacci sequence is below:

public class FibonacciDP {
    static final int MAX = 1000;
    public static void main(String[] args){
        int output = fibonacciDP(5);
        System.out.println(output);
    }
    public static int[] fib = new int[MAX];
    public static int fibonacciDP(int input){
        if(input == 0){
            return 0;
        }
        if(input == 1){
            return 1;
        }
        if(fib[input]!=0) return fib[input]; //return cached 
        fib[input] = fibonacciDP(input-1) + fibonacci(input-2);
        return fib[input];
    }
}

In this way, the time complexity of fibonacci sequence will become O(n).

Iterative:

public class FibonacciI {
     public static int fibonacciN(int input){
         int input1 = 0;
         int input2 = 1;
         int temp = 0;
         for(int i=0;i<input;i++){
             temp = input1;
                 input1 = input2;
             input2 = temp + input2;
         }
         return input1;
     }
}

I think the time complexity for iteration way is O(n), because you just need to sum the previous item and the one before the previous one for n times.

[GingerBear]

@dianadujing 有没有更好地方法？试着总结一下，分析一下复杂度？

[dianadujing]

@GingerBear CC150 has explanation for recursive algorithm, please check P108.

[GingerBear]

@dianadujing Why not share your own understanding here?

[dianadujing]

At the beginning, I was confused about the time complexity when recursion was used. Then I checked the book and found this. I thought you met the same condition as me....If you had already seen that, ignore what I said

[allen6432]

这里探讨一下时间复杂度 如果用楼上楼上的recursive way的话，时间复杂度是O{[(5^1/2)+1]^n/2^n}. 首先可以很容易看出一个上阶，那就是O（2^n). 如果要精确这个上阶，我们要回来看一下这个递推公式f(n+1)=fn+f(n-1)； 这个递推可以用正常的配系数的方法解，比较麻烦，这里不详细介绍了； 还有一个方法是用特征方程来解，这个递推的特征根是x^2-x-1=0; 得到两个特征根，然后可以得到复杂度的表达式。

如果要说到更好的code, 我能想到的就应该就只要矩阵的那个。在recursive 前提下能达到 lgn级别。

对于

[GingerBear]

@allen6432 欢迎怡波童鞋的加入，数学系出身的分析起来果然高大上，你能不能发一个新的issue跟我们讲讲如何用正确地方法分析一个算法的时间复杂度和空间复杂度？

感觉不少同学包括我都不是很清楚怎么做复杂度分析，平时分析起来总是只有一个泛泛感觉在哪里，很难做出令人信服的分析。

[dianadujing]

"时间复杂度是O{[(5^1/2)+1]^n/2^n}. "怎么做出这个结果的？@allen6432

[allen6432]

@GingerBear @dianadujing 不好意思，这几天没来逛。 我争取今晚写写怎么算时间复杂度的东西