解析西斐波那契数列通项公式斐波那契数列时间复杂度推导( 三 )

更多的阶乘型时间复杂度O(n!)的分析可以查看下文中的：如何理解阶乘型算法复杂度O(n!)？
如何理解斐波那契数列的时间复杂度O(2^N)?O(2^N)Math.pow(base, ex)，2个递归所以base是2 。N的话是因为N->∞，但其实真正是O(2^(N-1)) 。/** * @param {number} N * @return {number} */var fib = function (N) {/*** 解法1: 递归* 性能:88ms 34.2MB*/console.log('foo');if (N <= 1) return N;return fib(N - 1) + fib(N - 2)};N打印foo数O(2^N)11O(2^0)22^1 + 1O(2^1)32^2 + 1O(2^2 )42^3 + 1O(2^3 )52^4 + 1O(2^4 )
通过上表我们分析得到：如果包含1的话，严格来讲时间复杂度是O(2^(N-1)) 。如果从N>1开始计算，时间复杂度确实是O(2^N) 。斐波那契数列非常长，N->∞，因此可以将斐波那契数列的时间复杂度直接看做是O(2^N) 。
如何理解阶乘型时间复杂度O(n!)？O(N!)我们把上面的代码改造一下，增加一个count用来统计O(n!) 。
let count = 0;function nFacRuntimeFunc(n) {for(let i=0; i<n; i++) {count++;nFacRuntimeFunc(n-1);}}阶乘型O(n!)的时间复杂度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1) 的方式去计算。注意哦，这里是多个阶乘的和。不仅仅是n * (n-1) * (n-2) * (n-3)···1 。上述示例中的count即为复杂度的值。
n多次n! + (n-1)! + ··· + 1!countO(n!)111O(1)2(2!+1!) +(1!)4O(4)3(3!+(2!+1!)+1!)+((2!+1!)+1!)+(1!)15O(15)4…64O(64)5…325O(325)6…1956O(1956)7…13699O(13699)8…109600O(109600)9…986409O(986409)10…9864100O(9864100)
快看看这个表格吧，n为10的时候O(n!)达到了O(9864100)，接近了O(一千万) 。这种算法的性能真的是糟糕到极致了。

以上关于本文的内容，仅作参考！温馨提示：如遇健康、疾病相关的问题，请您及时就医或请专业人士给予相关指导!

「四川龙网」www.sichuanlong.com小编还为您精选了以下内容，希望对您有所帮助：

解析西斐波那契数列通项公式 斐波那契数列时间复杂度推导( 三 )

解析西斐波那契数列通项公式斐波那契数列时间复杂度推导( 三 )