斐波那契数列时间复杂度推导（解析西斐波那契数列通项公式） |
您所在的位置：网站首页 › 斐波那契数列时间复杂度证明过程 › 斐波那契数列时间复杂度推导（解析西斐波那契数列通项公式） |
斐波那契数列时间复杂度推导（解析西斐波那契数列通项公式）
|
正式工作也有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)。 对数型O(log n) 常用代码执行次数为x，n为目标数字。符合2^x=n，推导出x=log2(n)（log n）的情况 算法消耗随n的增长而增长，性能较好 let n = 100;let i = 1;while(i |
【本文地址】
今日新闻 |
推荐新闻 |