blocks|key|1507917|text|预先计算直到足够大的n的所有Fibonacci数，并生成源代码片段，用可以容纳这些数字的类型中的数字定义一个数组。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1507918|然后，您可以只检索数组中索引n中的值。这是O(1)。没有比这更快的了。|offset|length|style|CODE|1507919|entityMap^0|0|E|1|L|4|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@$D|L|E|M|F|G]|$D|N|E|O|F|G]]|9|@]|A|$]]|$1|H|3|-4|5|6|7|P|8|@]|9|@]|A|$]]]|I|$]]

Precalculate all Fibonacci numbers up to a sufficiently large number of n, and generate a source code snippet defining an array with the numbers in a type which can hold these numbers.

Then you can just retrieve the value in index <code>n</code> in your array. This is <code>O(1)</code>. Doesn't come much faster than that.

blocks|key|986453|text|试试dynamic+programming。创建一个保存第n-1个Fibonacci数的每个值的数组。第一次运行时，它花费的时间与普通Fibonacci函数一样长，但后续调用可以在O(1)中运行，因为数组中已经有了这个值。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|986454|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Dynamic_Programming#Fibonacci_sequence^0|2|J|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Try <a href="http://en.wikipedia.org/wiki/Dynamic_Programming#Fibonacci_sequence" rel="nofollow">dynamic programming</a>. Create an array that holds every value of the n-1th Fibonacci number. The first time it runs, it'll take about as long as a normal Fibonacci function, but subsequent calls can be run in O(1), since you'd already have the value in the array.

blocks|key|1507823|text|根据我的经验，分析版本在实践中通常非常快，但正如Rosetta代码所指出的那样，它只能准确到序列中的第92个数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1507824|递归版本需要指数时间来运行，所以即使对于中等大小的n，它也必然非常慢。迭代和尾递归函数在n中线性时间。可以从斐波那契序列的matrix+form推导出更快的O(lg+)时间算法。|offset|length|1507825|有关递归和尾递归算法的说明，请参阅SICP。|1507826|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form^0|0|1P|B|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

In my experience, the analytic version is usually very fast in practice, but as Rosetta code notes, it's only accurate up to the 92nd number in the sequence.

The recursive version takes exponential time to run, so it's bound to be very slow even for moderately-sized n. The iterative and tail-recursive functions take time linear in n. A faster, O(lg n) time algorithm can be derived from the <a href="https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form" rel="nofollow">matrix form</a> of the Fibonacci sequence.

See SICP for an explanation of the recursive and tail-recursive algorithm.

blocks|key|2007866|text|像往常一样，答案是“视情况而定”。一般来说，你不能真正存储那么多斐波那契数，因为它们往往增长得相当快--事实上，正如你的链接的分析部分所揭示的那样，它们是指数级的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2007867|因此，对于大多数实际目的，答案是“不计算--缓存”。也就是说，使用查找表。(通常情况下，在溢出之前需要少于100个条目。)|2007868|对于传统的存储方法，除了递归计算之外，您不会做得更好，因为它是O(d%5E2)，其中d是输出的位数--更复杂的任意大小的数字操作将很难与之竞争。|2007869|"Analytic“可能是较慢的方法之一，因为基数不方便，而且您会丢弃快速的整数数学运算。|2007870|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

The answer is, as usual, "it depends". Generally you can't really store that many Fibonacci numbers since they tend to increase rather rapidly -- in fact, exponentially as exposed by the Analytic sections of your link.

So, for most practical purposes the answer is "don't compute -- cache." That is, use a lookup table. (Typically you'll need less than 100 entries before an overflow, anyways.)

For conventional storage methods, you're not going to do much better than just recursively computing it, as it's O(d^2) where d is the number of digits of output -- something that more complex arbitrary-sized number operations will have a hard time competing with.

"Analytic" is likely one of the slower methods since the bases are inconvenient and you'll be throwing away fast integer math.

blocks|key|986002|text|虽然您确实特别针对Java，但我昨晚在Python3中研究了这一点的不同实现。特别是，我研究了朴素的递归实现和分析实现(我称其为封闭形式的实现)。下面是代码，不需要我的单元测试：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|986003|import+math
from+timeit+import+Timer

def+fib_recursive(n):
++++"""
++++++++Compute+the+Fibonacci+sequence+from+a+given+number+n
++++"""
++++if+n+<+2:
++++++++return+n
++++else:
++++++++return+fib_recursive(n+-+2)+%2B+fib_recursive(n+-+1)

def+fib_closed_form(n):
++++"""
++++++++Compute+the+Fibonacci+sequence+using+a+closed+form.
++++"""
++++def+calc_golden_ratio():
++++++++return+(1+%2B+math.sqrt(5))+/+2

++++gr+=+calc_golden_ratio()
++++inverse_gr+=+1+-+gr
++++numerator+=+math.pow(gr,++n)+-+math.pow(inverse_gr,++n)
++++return+numerator+//+math.sqrt(5)

if+__name__+==+'__main__':
++++for+n+in+range(0,++10):
++++++++n+=+str(n)
++++++++time+=+Timer("fib_closed_form("+%2B+n+%2B+")",++"from+__main__+import+fib_closed_form")
++++++++print('Fib_Closed_Form('+%2B+n+%2B')+=+'+%2B+str(time.timeit()))
++++++++time+=+Timer("fib_recursive("+%2B+n+%2B+")",++"from+__main__+import+fib_recursive")
++++++++print('Fib_Recursive('+%2B+n+%2B')+=+'+%2B+str(time.timeit()))|code-block|syntax|javascript|986004|下面是那些值在1-10之间的函数的时间(时间以秒为单位，使用timeit模块测量)。每一次调用默认由timeit模块进行1000000次，所以它是所有调用总共花费多长时间的结果：|offset|length|986005|Python+3.2.2+(default,+Nov+21+2011,+16:50:59)+
[GCC+4.6.2]+on+staggerlee,+Standard
>>>+
Fib_Closed_Form(1)+=+5.808775901794434
Fib_Recursive(1)+=+0.6938691139221191

Fib_Closed_Form(2)+=+6.142783880233765
Fib_Recursive(2)+=+1.9276459217071533

Fib_Closed_Form(3)+=+6.62189793586731
Fib_Recursive(3)+=+3.6403379440307617

Fib_Closed_Form(4)+=+6.376585960388184
Fib_Recursive(4)+=+6.733421802520752

Fib_Closed_Form(5)+=+6.566863059997559
Fib_Recursive(5)+=+11.409136056900024

Fib_Closed_Form(6)+=+6.521269083023071
Fib_Recursive(6)+=+18.514809131622314

...

Fib_Closed_Form(10)+=+6.631903886795044
Fib_Recursive(10)+=+131.51839208602905|986006|正如您所看到的，这种封闭形式具有较高的前期成本。递归的那个把它踢出了水面！不过，只有在n=4的情况下，它才能保持竞争力。你可以看到它的时机变得越来越糟糕了。当我们达到n=+6左右时，我们已经可以看出这不是正确的方向。|986007|顺便说一下，我昨晚尝试了n=+25。关闭的表单花费了大约相同的时间，并且递归表单在我上床之前没有完成(至少运行了半个小时)。|986008|我的观点是，这些都是相当容易实现的，并且可以很直接地提出一些单元测试。您可以尝试一下，并在Java中亲自查看结果，尽管在Java这样的语言中计时可能会很复杂，而不需要额外的设置。|986009|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.python.org/library/timeit.html^0|0|0|U|6|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|12|8|@]|9|@$I|13|J|14|1|15]]|A|$]]|$1|K|3|L|5|D|7|16|8|@]|9|@]|A|$E|F]]|$1|M|3|N|5|6|7|17|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|18|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|19|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|T|$U|$5|V|W|X|A|$Y|Z]]]]

While you did target this at Java in particular, I was looking at different implementations of this in Python 3 last night. In particular, I looked at the naive recursive implementation and the analytic one (I called it the closed form one however). Here is the code, sans my unit test for it:

<pre><code>import math
from timeit import Timer

def fib_recursive(n):
 """
 Compute the Fibonacci sequence from a given number n
 """
 if n &lt; 2:
 return n
 else:
 return fib_recursive(n - 2) + fib_recursive(n - 1)

def fib_closed_form(n):
 """
 Compute the Fibonacci sequence using a closed form.
 """
 def calc_golden_ratio():
 return (1 + math.sqrt(5)) / 2

 gr = calc_golden_ratio()
 inverse_gr = 1 - gr
 numerator = math.pow(gr, n) - math.pow(inverse_gr, n)
 return numerator // math.sqrt(5)

if __name__ == '__main__':
 for n in range(0, 10):
 n = str(n)
 time = Timer("fib_closed_form(" + n + ")", "from __main__ import fib_closed_form")
 print('Fib_Closed_Form(' + n +') = ' + str(time.timeit()))
 time = Timer("fib_recursive(" + n + ")", "from __main__ import fib_recursive")
 print('Fib_Recursive(' + n +') = ' + str(time.timeit()))
</code></pre>

Here are the timings for those functions with values from 1-10 (time is in seconds, measured using the <a href="http://docs.python.org/library/timeit.html" rel="nofollow">timeit</a> module). Each call is made by the timeit module 1000000 times by default, so it is the result of how long all the calls in total takes:

<pre><code>Python 3.2.2 (default, Nov 21 2011, 16:50:59) 
[GCC 4.6.2] on staggerlee, Standard
&gt;&gt;&gt; 
Fib_Closed_Form(1) = 5.808775901794434
Fib_Recursive(1) = 0.6938691139221191

Fib_Closed_Form(2) = 6.142783880233765
Fib_Recursive(2) = 1.9276459217071533

Fib_Closed_Form(3) = 6.62189793586731
Fib_Recursive(3) = 3.6403379440307617

Fib_Closed_Form(4) = 6.376585960388184
Fib_Recursive(4) = 6.733421802520752

Fib_Closed_Form(5) = 6.566863059997559
Fib_Recursive(5) = 11.409136056900024

Fib_Closed_Form(6) = 6.521269083023071
Fib_Recursive(6) = 18.514809131622314

...

Fib_Closed_Form(10) = 6.631903886795044
Fib_Recursive(10) = 131.51839208602905
</code></pre>

As you can see, the closed form of this has a higher up-front cost. The recursive one blows it out of the water! It only stays competitive up through a value of n = 4 though. You can see it's timing becoming worse and worse though. By the time we get up to around n = 6, we can already see this is not the right direction.

By the way, I attempted an n = 25 last night. The closed form took about the same amount of time, and the recursive form did not finish before I went to bed (at least half an hour of running).

My point is that these are fairly easy to implement, as well as straightforward to come up with some unit tests for. You can give it a shot and see the results for yourself in Java, though timing things in a language such as Java can be complex without additional setup.

Is it known what is the fastest Java algorithm for calculating nth term of Fibonacci sequence ? 

I have found <a href="http://rosettacode.org/wiki/Fibonacci_sequence#Java" rel="nofollow">these algorithms</a> . I guess that Iterative algorithms should be faster than Recursive and Analytic algorithms .

The fastest Java algorithm for calculating nth term of Fibonacci sequence?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

知道计算斐波那契数列第n项的最快的Java算法是什么吗？我找到了。我猜迭代算法应该比递归和分析算法更快。

问计算斐波那契数列第n项的最快Java算法？
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算斐波那契数列第n项的最快Java算法？EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算斐波那契数列第n项的最快Java算法？
EN