斐波那契数列问题时间复杂度较低的解法

2020-03-05 本文已影响0人我要牛肉面面

先甩一个在线练习的地址：牛客网

题目描述
给出一个整数 n，请输出斐波那契数列的第 n 项对 1e9 + 7 取模的值。
斐波那契数列的前几项（从第0项开始）为：[0, 1, 1, 2 ,3 ,5 ,8 ,13, ...]
n的取值范围：1 <= n <= 1e18，且有4秒和512MB内存的限制。

题目的原标题为

斐波那契数列问题的递归和 动态规划

这个标题实际上存在着一定的误导性。
递归解法的主要思路是直接套用F(n) = F(n-1) + F(n-2)这个公式，将F(n)拆分为多个1按一定顺序相加，时间复杂度为O(F(n))。动态规划的主要思路是保存F(1), F(2), ..., F(n-1)的值，使得每次计算F(k)的时候都只需要做一次加法运算，时间复杂度为O(n)。
但是这里n的取值范围较大，既不可能存储所有的F(k)，也来不及把它们全部计算一遍，因此需要一种时间复杂度小于O(n)，最好为O(log(n))甚至O(1)的解法。

那么自然而然就会产生两种思路：

借助F(k)及其附近的几个值来表示F(2k)和F(2k+1)，
借助F(1), F(2), F(4), F(8), ...等值来表示F(k)。

后一种思路我没想到具体应该如何实施，这里直接复制别人的说法：

f(n) = f(n-1) + f(n-2)
f(n-1) = f(n-1)
矩阵：
[ f(n) ] = [ 1*f(n-1) + 1*f(n-2) ] = [ 1 1 ] * [ f(n-1) ]
[ f(n-1) ] [ 1*f(n-1) + 0*f(n-2) ] [ 1 0 ] [ f(n-2) ]
显然：
[ f(2) ] = [ 1 ]
[ f(1) ] [ 1 ]
假设：
mul = [[ 1, 1 ], [ 1, 0 ]]
那么：
[ f(n), f(n-1) ]T
= mul * [ f(n-1), f(n-2) ]T
= mul * mul * [ f(n-2), f(n-3) ]T
= ...
= mul^(n-2) * [ f(2), f(1) ]T
转变为快速幂问题：
快速求 mul^(n-2) 的值即可

快速求有限大小矩阵的n次幂问题显然是动态规划，且时间和空间复杂度均为O(log(n))，具体编码留作练习。
反正我拿到题目就直接顺着第一种思路想下去了：

f(k) = f(k-1) + f(k-2) = f(k-2) + f(k-3) + f(k-2)
= 2f(k-2) + f(k-3) = 2*(f(k-3) + f(k-4)) + f(k-3)
= 3f(k-3) + 2f(k-4) = 3*(f(k-4) + f(k-5)) + 2f(k-4)
= 5f(k-4) + 3f(k-5) = ...
= f(a+1) * f(k-a) + f(a) * f(k-a-1) for a in range(1,k-1)

f(2k+1) = f(k) * f(k) + f(k+1) * f(k+1)
f(2k) = f(k) * (f(k-1) + f(k+1))

因此也可以借助递归和动态规划的思路，只求解f(n/2)附近的2--3个值，f(n/4)附近的3--4个值，f(n/8)附近的3--4个值……且这些值可以由小到大依次求出，整个算法的时间和空间复杂度均为O(a*log(n))，其中a的数量级不会太高，可能在O(1)到O(log(n))之间，但我不会证明。。。手动捂脸。

由于不知道在线练习/笔试的环境能否使用NumPy等库，于是手写了一个最简单的稀疏一维列表class，其中又手写了一个折半查找法，于是又是连编码带debug一个晚上过去了。。。
上最终代码：

import os

M = 10 ** 9 + 7

def add_mod(a, b):
    r = a + b
    if r < 0 or r >= M:
        r = r % M
    return r

def mul_mod(a, b):
    r = a * b
    if r < 0 or r >= M:
        r = r % M
    return r

class SparseList():
    indices = []
    data = []
    
    def __init__(self, ls):
        self.indices = [0, ]
        self.data = [ls, ]
    
    def _binary_search(self, data, fromlist):
        if l <= 1:
            return 0
        l2 = l // 2
        if data < fromlist[l2]:
            r = self._binary_search(data, fromlist[:l2])
        else:
            r = l2 + self._binary_search(data, fromlist[l2:])
        return r
    
    def get(self, idx):
        indices_idx = self._binary_search(idx, self.indices)
        idx_offset = idx - self.indices[indices_idx]
        if idx_offset >= len(self.data[indices_idx]):
            raise IndexError
        else:
            return self.data[indices_idx][idx_offset]
    
    def put(self, idx, dt): # set value
        indices_idx = self._binary_search(idx, self.indices)
        idx_offset = idx - self.indices[indices_idx]
        l = len(self.data[indices_idx])
        if idx_offset > l:
            indices_idx_1 = indices_idx + 1
            if indices_idx_1 < len(self.indices)
               and idx == self.indices[indices_idx_1] - 1:
                self.indices[indices_idx_1] = idx
                self.data[indices_idx_1].insert(0, dt)
            else:
                self.indices.insert(indices_idx_1, idx)
                self.data.insert(indices_idx_1, [dt,])
        elif idx_offset == l:
            self.data[indices_idx].append(dt)
        else:
            self.data[indices_idx][idx_offset] = dt
    
    def toString(self):
        return '[%s]' % (
                   ', '.join(
                       ['%d: %s' % (i, str(j))
                           for i,j in zip(self.indices, self.data)
                       ]
                   )
               )
    
    def pretty(self):
        return ('[%s' + os.linesep + ']') % (
                   (',' + os.linesep + ' ').join(
                       ['%d: %s' % (i, str(j))
                           for i,j in zip(self.indices, self.data)
                       ]
                   )
               )

class FiboMod():
    data = SparseList([0, 1, 1, 2 ,3 ,5 ,8 ,13, 21, 34, 55, 89])

    def fibo_mod_no_data(self, n):
        try:
            return self.data.get(n)
        except IndexError:
            (a, b, c) = (0, n // 2, n % 2)
            if c:
                c += b
                (b, c) = tuple(self.fibo_mod_no_data(i) for i in [b, c])
                r = add_mod(mul_mod(b, b), mul_mod(c, c))
            else:
                (a, c) = (b - 1, b + 1)
                (a, b, c) = tuple(self.fibo_mod_no_data(i) for i in [a, b, c])
                r = mul_mod(b, add_mod(a, c))
            self.data.put(n, r)
            return r

FIBO = FiboMod()
    
def main():
    n = int(input().rstrip().split()[0])
    print(FIBO.fibo_mod_no_data(n))

if __name__ == '__main__':
    main()

启示：

思考一个好的算法，比一有想法就编码更好。
有了想法一定要编码，不要眼高手低，不然连折半查找都写不对，即使以前写的同一段代码没有任何问题且工作良好。

2021-06-07更新：
折半查找这么常见/常用的算法，Python当然是有相应的库的，也就是bisect：
https://docs.python.org/2.7/library/bisect.html
于Python 2.1中新增，提供以下方法：

bisect.bisect_left(a, x, lo=0, hi=len(a))
假定列表a是有序的，在a[lo:hi]中查找并返回一个下标i，使得a.insert(i, x)后仍然有序，且当x == a[i]时，x被插入到原有元素的左侧。
bisect.bisect_right(a, x, lo=0, hi=len(a))
与bisect_left类似，但是当x == a[i]时，x被插入到原有元素的右侧。
bisect.insort_left(a, x, lo=0, hi=len(a))
消耗O(log(n))时间执行bisect_left，然后消耗O(n)时间插入元素x，使a[lo:hi]保持有序。
bisect.insort_right(a, x, lo=0, hi=len(a))
与insort_left类似，但是当x == a[i]时，x被插入到原有元素的右侧。

斐波那契数列问题时间复杂度较低的解法

猜你喜欢

热点阅读