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

文章插图
正式工作也有3年的时间了，想要写出更加优雅的代码。
所以最近在刷leetcode补充数据结构和算法方面的知识。
学校里虽然学过，但是仅仅是有个大概的认识。只有实际工作过几年以后，才会明白数据结构和算法的重要性。
如果是通信专业出身的同学，或者是硬件出身的同学一定知道：对于一个信号，我们可以从时域和频域两个方面去分析。
那么计算机科学或者说软件开发中的算法怎么去分析呢？有两个衡量优劣的维度：时间复杂度和空间复杂度。
时间复杂度：执行当前算法所消耗的’时间’ 。空间复杂度：执行当前算法所占用的内存。在这边博文中，我们来好好分析一下时间复杂度。
时间复杂度真的是计算’时间’吗？时间复杂度公式：大O符号表示法常见时间复杂度类型及代码分析常数型O(1)对数型O(log n)线性型O(n)线性对数型O(n log n)平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)平方底指数型O(2^n)、立方底指数型O(3^n)、K次底指数型O(k^n)阶乘型O(n!)如何理解斐波那契数列的时间复杂度O(2^N)?如何理解阶乘型时间复杂度O(n!)？参考资料时间复杂度真的是计算’时间’吗？把算法的执行时间当做时间复杂度？
这种方式是最为直观也是最容易想到的方式。
但是有一个问题，那就是代码在不同性能的机器上运行，以及在不同的状态下运行，会呈现出完全不同的运行时间。比如说我有一台内存为32GB内存的mbp，还有一台8GB的台式机，假设其它的硬件条件比如cpu，主板以及机器负载状态一致。通常情况下，32GB的内存要比8GB的内存运行更快。而且这种理想状态下的只有单一变量的状态也是很难做到的。
所以不能通过计算算法的消耗时间作为时间复杂度。
那我们通常所说的’时间’复杂度中的’时间’到底是指什么呢？
聪明的前辈们想到了一种方式：大O表示法。
大O表示法内部有非常复杂的数学计算逻辑，我们偷个懒，不去证明公式，把公式用好就很厉害了。
为什么不去证明一下或者演算一遍？我在大一曾经上过一门叫做高等代数的课，有道题目叫做：请证明1+1=2 。
看到这个题目应该知道为什么不深究大O表示法背后的数学了吧。
时间复杂度公式：大O符号表示法T(n) = O(f(n))f(n)是指每行代码执行次数之和f(n)可以是这些值：1，log n，n，nlog n，n^2，n^3，n^k，2^n，n!f(n)与O正相关O(f(n))可以是这些值：O(1)，O(log n)，O(n)，O(nlog n)，O(n^2)，O(n^3)，O(n^k)，O(2^n)，O(n!)大O表示法实际表示的是代码执行时间的增长变化趋势，不是真实的运行时间，是一种趋势预估大O表示法中的f(n)是近似值。很多时候不会完全是1，log n，n，nlog n，n^2，n^3，n^k，2^n，n!这些完整的值。例如斐波那契数列的真实时间复杂度为O(2^N-1)，由于N->∞，所以可以近似为O(2^N) 。更多的斐波那契数列时间复杂度的分析可以查看下文中的：如何理解斐波那契数列的时间复杂度O(2^N)?
常见时间复杂度类型及代码分析理论扯了一大堆了，到精彩绝伦的Show me the code环节了。先来看一张大O复杂度曲线图。
以下时间复杂度根据最佳->较好->一般->较差->糟糕的顺序排列。
常数型O(1)对数型O(log n)线性型O(n)线性对数型O(n log n)平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)平方底指数型O(2^n)、立方底指数型O(3^n)、K次底指数型O(k^n)阶乘型O(n!)常数型O(1)常见于赋值和引用等简单操作算法消耗不随变量增长而增长，性能最佳无论代码执行多少行，即使有几千几万行，时间复杂度都为O(1)实际开发过程中，一次递归的时间复杂度也为O(1) 。因为O(1^n)无论n为多少都为O(1)let i = 0;let j = 9;i++;j--;let k = i + j;代码分析： i为1，j为10，k为11 。时间复杂度为O(1) 。

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

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

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

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