美文网首页程序猿阵线联盟-汇总各类技术干货程序员
Fibonacci数列高效解法大全及时间复杂度分析 连载【6】

Fibonacci数列高效解法大全及时间复杂度分析 连载【6】

作者: FSS_Sosei | 来源:发表于2018-10-12 21:40 被阅读176次
    在数学上,斐波那契数列是以递归的方法来定义

    ……续上回Fibonacci数列高效解法大全及时间复杂度分析 连载【5】

    在GMP库里就有斐波那契数和数列的单独函数

    11.  GMP内置fib函数解法

    这直接引用就可以了

    import gmpy2

    def Fibonacci_sequence_09 (n: int) -> int:  #参数n是表示求第n项Fibonacci数

        '返回单项的GMP内置fib函数解法'

        assert isinstance(n, int), 'n is an error of non-integer type.'

        if n>=0:

            return gmpy2.fib(n)

        else:

            return None

    Fibonacci_sequence_09(1000000)

    看一下耗时多少,同上例

    Total time: 0.004522秒

    算第100万项Fibonacci数用时只有二分递归解法的65.6%。果然更快速一些

    GMP和Mathematica内置算Fibonacci数的函数都是用的同一种快速算法

    是一种叫二进制模幂算法,让我们来看看是什么样

    https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm

    引自GMP官网上的资料,用的是这个递推式

    把n分解为n的二进制表示形式,然后直接迭代递推。递推迭代是O(log n),大整数乘方是O(n*log n)),那么整个算法时间复杂度也是O(n*(log n)^2)的

    那为什么表现的比同样O(n*(log n)^2)的二分迭代解法更快呢

    可以看这篇《为什么算法渐进复杂度中对数的底数总为2》解释

    12.  二进制模幂解法

    好,不用GMP那C写Fibonacci数库函数,用Python实现一遍这个二进制模幂解法(当然大数运算还是用到GMP)

    我来写出来

    import gmpy2

    def Fibonacci_sequence_10 (n: int) -> int:  #参数n是表示求第n项Fibonacci数

        assert isinstance(n, int), 'n is an error of non-integer type.'

        def Calculate_Fibonacci_sequence (n: int) -> int:

            '返回单项的二进制模幂解法'

            if n >= 1 :

                add_on = (2, -2)  #就是 2*(-1)^k 这项

                prev_num, current_num = gmpy2.mpz(1), gmpy2.mpz(1)  #设prev_num为F[1],current_num为F[2]

                for i in range(gmpy2.bit_length(n) - 1, 0, -1):  #从最高位开始遍历除末位外的每个二进制位

                    if gmpy2.bit_test(n, i):  #注意bit_test的i参数0就是第一位(二进制表示的最末尾一位)

                        prev_num = current_num - prev_num  #prev_num = F[2k] = F[2k+1] - F[2k-1],current_num就是等于F[2k+1]

                    else:

                        current_num = current_num - prev_num  #prev_num就是等于F[2k-1],current_num = F[2k] = F[2k+1] - F[2k-1]

                    sq_prev_num = prev_num ** 2; sq_current_num = current_num ** 2

                    prev_num = sq_prev_num + sq_current_num  #F[2k-1] = F[k]^2 + F[k-1]^2

                    current_num = sq_current_num * 4 - sq_prev_num + add_on[1 if gmpy2.bit_test(n, i) else 0]  #F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k

                if n & 1 == 0:  #迭代完成,再对末位做个判断

                    current_num = current_num - prev_num

                return current_num

            elif n == 0:

                return 0

        if n >=0:

            return Calculate_Fibonacci_sequence(n)

        else:

            return None

    Fibonacci_sequence_10(1000000)

    看耗时多少,同上例

    Total time: 0.005285秒

    只比纯C库实现的慢了不到1ms,Python还是不错的

    未完待续……

    Fibonacci数列高效解法大全及时间复杂度分析 连载【7】

    相关文章

      网友评论

        本文标题:Fibonacci数列高效解法大全及时间复杂度分析 连载【6】

        本文链接:https://www.haomeiwen.com/subject/dvuqaftx.html