Fibonacci数，Θ(log n)
作者：infinte 来源：infinte博客 发布时间：2010-03-28 13:28:00
标签：Fibonacci,函数,数学,算法
生成Fiboncci Fn数有Θ(1)，Θ(n)甚至指数级的算法，不过有Θ(log n)的吗？告诉你，有。
首先，关于Fibonacci数，有下面的定理（假设F0 = 0，n≥2）
证明可以用归纳法，n=2时不证自明，假设n=k-1时成立，那么n=k时，
现在，计算F(n)的问题就转化到计算矩阵
上来。不过现在问题已经很明晰了——反复平方法。
下面是js源码：
var fib = function() {var f = function(n, a, b, p, q) {if (n == 0) return b;if (n & 1) return f(n - 1, b * q + a * q + a * p, b * p + a * q, p, q)else return f(n >>> 1, a, b, q * q + p * p, q * (2 * p + q));}return function(n) {return f(n, 1, 0, 0, 1)};}();
0
投稿猜你喜欢
- Python 是一种美丽的语言，它简单易用却非常强大。但你真的会用 Python 的所有功能吗？任何编程语言的高级特征通常都是通过大量的使用
- string 对象 1、str.match(RegExp) 在str中搜索匹配RegExp的字符串并保存在一个数组内返回， 如果RegExp
- 案例一：运行下面的代码结果是什么？class Person: def run(self): &nbs
- 本文实例讲述了python实现提取百度搜索结果的方法。分享给大家供大家参考。具体实现方法如下：# coding=utf8import url
1、Matplotlib 简介数据可视化有助于更有效地讲述有关数据的故事并使其易于呈现。有时很难用静态图表来解释数据的变化，为此，我们将讨论- 说下防止PHPDDOS发包的方法 if (eregi("ddos-udp",$read)) { fputs($verbi
- 在做数据库修改或删除操作中，可能会导致数据错误，甚至数据库奔溃，而有效的定时备份能很好地保护数据库。本篇文章主要讲述Navicat for
- 一、导出数据库用mysqldump命令（注意mysql的安装路径，即此命令的路径）：1、导出数据和表结构：mysqldump -u用户名 -
- 作为python和机器学习的初学者，目睹了AI玩游戏的各种风骚操作，心里也是跃跃欲试。然后发现微信跳一跳很符合需求，因为它不需要处理连续画面
- 本文实例讲述了python实现简单ftp客户端的方法。分享给大家供大家参考。具体实现方法如下：#!/usr/bin/python# -*-
- 背景最近尝试了解Django中ORM实现的原理，发现其用到了metaclass(元类)这一技术，进一步又涉及到Python class中有两
- 两个进程发生死锁的典型例子是：进程T1中获取锁A，申请锁B；进程T2中获取锁B，申请锁A，我们下面动手来演示一下这种情况：1. 创建一个Da
- filter(function or None, sequence)，其中sequence 可以是list ,tuple,string。这个
- 一:模版的继承1.什么是模板继承?你需要事先在你想要使用的主页面上划定区域做好标记，之后在子页面继承的时候你就可以使用在主页面划定的区域，也
- 首先编写py程序:printtest.pydef test(): print('print test')将以上.
- 由于刚刚学习python，对PyCharm也不是很熟悉，在成功运行多个死循环程序而没有关闭它的情况下，PyCharm成功的经常无响应，反应缓
- 在已经发表的系列文章中我们已经讨论了两个ASP对象：Application对象和Session对象，因此能够访问Application对象和
- 我的第一个用于生产环境的perl脚本,虽然不是很优秀,但也迈出了扎实的一步 :)领导有任务,给一批IP列表,ping每一台机器,如果没有响应
- 本文详细介绍了Python中类型关系和继承关系。分享给大家供大家参考。具体分析如下：如果一个对象A持有另一个对象B的ID，那么检索到A之后就
- 通常我们提交代码一般都是 git add ，git commit -m, git push的这么个流程。添加到暂存区
