斐波那契数列数列（Fibonacci sequeuece）,又称黄金分割数列、兔子数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、 .......
  在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
  关于该数列的代码实现实际上是有三种方式：（目前只学会了两种比较简单的）

实现一

///  最慢的一种方式  时间复杂度 O(2^n)
/// @param n 下标
+ (NSInteger)slowFibonacciValueWithIndex:(NSInteger)n
{
    if (n == 0 || n == 1) {
        return n;
    }
    return [self slowFibonacciValueWithIndex:n - 1] + [self slowFibonacciValueWithIndex:n - 2];
}

  这种方式的实现是最直接的一种方式，但是时间复杂度是O(2^n)，当数据规模在计算第40 以后结果时，其运行速度已经很慢了。

实现二

/// 一般的一种方式  时间复杂度O(n)
/// @param n 下标
+ (NSInteger)normalFibonacciValueWithIndex:(NSInteger)n
{
    if (n == 0 || n == 1) {
        return n;
    }
    
    NSInteger first = 0;
    NSInteger second = 1;
    
    for (NSInteger i = 2; i <= n; i++) {
        NSInteger sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

  这种方式其实也很容易理解，而且时间复杂度是O(n)级别的。相对来说还是不错的。一般掌握这两种就基本够用了。当然第三种方式时间复杂度是O(logn)级别的，算法速度更快，但是也最不容易理解。此处附上第三种方式，有心人可以继续研究研究

求斐波那契数列的三种方法