什么是斐波那契数列?

摘自《维基百科》
 
斐波那契数列（意大利语：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐波那契数列、黄金分割数列。
 
在数学上，费波那契数列是以递归的方法来定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）
 
用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

摘自《百度百科》
 
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
 
定义：
 
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
 
这个数列从第3项开始，每一项都等于前两项之和。
 
斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。

看了这么多简介之后，其实说的简单点斐波那契数列就是一系列数字，从第三项开始当前项等于前两项之和。下面我用OC给出斐波那契数列

第一种方式：

斐波那契数列递归调用，指数级增长2^n。递归方式效率低，时间复杂度是指数级的。

/**
 斐波那契数列递归调用，指数级增长2^n
 */
- (NSUInteger)Fibonacci:(NSUInteger)n {
    if (n < 2) {
        return n;
    }
    else {
        return [self Fibonacci:n-1] + [self Fibonacci:n-2];
    }
}

第二种方式：

用数组保存之前计算过的结果，减少大量重复计算，这样算法复杂度优化为 O(n)。

- (NSUInteger)Fibonacci2:(NSUInteger)n {
    if (n < 2) {
        return n;
    }
    else {
        NSMutableArray *array = [NSMutableArray arrayWithCapacity:n + 1];
        array[0] = @(0);
        array[1] = @(1);
        
        for (int i = 2; i < array.count; i++) {
            array[i] = @([array[i - 1] unsignedIntegerValue] + [array[i - 2] unsignedIntegerValue]);
        }
        
        return [array[n] unsignedIntegerValue];
    }
}

第三种方式：

同样是斐波那契数列，由于实际只有前两个计算结果有用，我们可以使用中间变量来存储，这样就不用创建数组以节省空间。同样算法复杂度优化为 O(n)。

- (NSUInteger)Fibonacci3:(NSUInteger)n {
//    NSDate *now1 = [NSDate date];
    if (n < 2) {
        return n;
    }
    else {
        NSUInteger a = 0, b = 1;
        for (int i = 1; i < n; i++) {
            b = a + b;
            a = b - a;
        }
//        NSLog(@"fb3耗时：%lf", [now1 timeIntervalSinceNow]);
        return b;
    }
}

第四种方式：

通过使用矩阵乘方的算法来优化斐波那契数列算法。算法的时间复杂度可以优化为O(log n)。

// 计算二阶矩阵的相乘
- (NSArray *)multiArrayA:(NSArray *)arrayA arrayB:(NSArray *)arrayB {
    
    // 定义一个空的二阶矩阵
    NSMutableArray *arrayC = [NSMutableArray arrayWithObjects:@[@0,@0].mutableCopy,@[@0,@0].mutableCopy, nil];
    
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                NSNumber *numA = arrayA[i][k];
                NSNumber *numB = arrayB[k][j];
                NSNumber *numC = arrayC[i][j];
                
                // 新二阶矩阵的值计算
                numC = @(numC.unsignedIntegerValue + numA.unsignedIntegerValue * numB.unsignedIntegerValue);
                
                [arrayC[i] replaceObjectAtIndex:j withObject:numC];
            }
        }
    }
    return arrayC;
}

- (NSUInteger)Fibonacci4:(NSUInteger)n {
    
//    NSDate *now2 = [NSDate date];
    // 结果矩阵  最开始的结果矩阵也可以看做是1，因为这个矩阵和任意二阶A矩阵相乘结果都是A
    NSArray *arrayA = [NSArray arrayWithObjects:@[@1,@0],@[@0,@1], nil];
    
    // 元矩阵，这里可以把元矩阵看做是2**0=1
    NSArray *arrayB = [NSArray arrayWithObjects:@[@1,@1],@[@1,@0], nil];
    
    while (n) {
        // 取n的二进制的最后一位和1做与运算，如果最后一位是1，则进入if体内部
        if (n & 1) {
            // 如果在该位置n的二进制为1，则计算ans和base矩阵
            arrayA = [self multiArrayA:arrayA arrayB:arrayB];
        }
        // base矩阵相乘，相当于初始base矩阵的幂*2
        arrayB = [self multiArrayA:arrayB arrayB:arrayB];
        // n的二进制往右移一位
        n >>= 1;
    }
    NSNumber *result = arrayA[0][1]; // 最后获取到的二阶矩阵的[0][1]即f(n)的值
//    NSLog(@"fb4耗时：%lf", [now2 timeIntervalSinceNow]);
    return result.unsignedIntegerValue;
}

参考资料

算法之矩阵计算斐波那契数列