对数型O(log n)常用代码执行次数为x,n为目标数字 。符合2^x=n,推导出x=log2(n)(log n)的情况算法消耗随n的增长而增长,性能较好let n = 100;let i = 1;while(i<n){i = i * 2}代码分析: i为128 。n为100,时间复杂度为O(log2(100)) 。因为Math.log2(100)≈6.64,所以最终的时间复杂度为O(6.65) 。
线性型O(n)常见于一次for循环,while循环算法消耗随n的增长而增长,性能一般无论n值有多大,即使是Inifinity,时间复杂度都为O(n)let n = 100;let j = 0;for(let i = 0;i<n;i++){j = i;}代码分析: i为100,j为99 。n为100,时间复杂度为O(100) 。
线性对数型O(n log n)常用于一个对时间复杂度为O(log2(n))的代码执行一个n次循环算法消耗随n的增长而增长,性能较差let n = 100;for(let m = 0; m<n; m++){let i = 1;while(i<n){i = i * 2}}代码分析: i为128 。m为100,n为100,时间复杂度为O(m log2(n)) 。因为100* Math.log2(100)≈664.39,所以最终的时间复杂度为O(664.39) 。
平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)最常见的算法时间复杂度,可用于快速开发业务逻辑常见于2次for循环,或者3次for循环,以及k次for循环算法消耗随n的增长而增长,性能糟糕实际开发过程中,不建议使用K值过大的循环,否则代码将非常难以维护let n = 100let v = 0;for(let i =0;i<n;i++){for(let j = 0; j<n; j++){v = v+j+i;}}代码分析: v为990000,i为100,j为100. n为100,时间复杂度为O(100^2) 。也就是O(10000) 。
立方型O(n^3)、K次方型O(n^k)和平方型O(n^2)类似,无非是多了几次循环 。
// 立方型O(n^3)for(let i =0;i<n;i++){for(let j = 0; j<n; j++){for(let m = 0; m<n; m++){}}}// K次方型O(n^k)for(let i =0;i<n;i++){for(let j = 0; j<n; j++){for(let m = 0; m<n; m++){for(let p = 0; p<n; p++){... // for循环继续嵌套下去,k值不断增大}}}}平方底指数型O(2^n)、立方底指数型O(3^n)、K次底指数型O(k^n)常见于2次递归的情况,3次递归以及k次递归的情况算法消耗随n的增长而增长,性能糟糕实际开发过程中,k为1时,一次递归的时间复杂度为O(1) 。因为O(1^n)无论n为多少都为O(1) 。斐波那契数列(兔子数列、黄金分割数列):1、1、2、3、5、8、13、21、34··· 题目:leetcode 509 斐波那契数
题解:509.斐波那契数
/** * @param {number} N * @return {number} */var fib = function (N) {/*** 解法1: 递归* 性能:88ms 34.2MB* 时间复杂度:O(2^N)*/if (N <= 1) return N;return fib(N - 1) + fib(N - 2);};假设N等于100 。代码分析: 结果为 xxx 。因为浏览器直接卡死 。nodejs中也运行不出来 。具体原因则是2的100次方真的太大了 。算不来 。N为100,时间复杂度为O(2^100) 。因为Math.pow(2, 100)= 1.2676506002282294e+30,所以最终的时间复杂度为O(1.2676506002282294e+30) 。大到爆表 。
立方底指数型O(3^n)、K次底指数型O(k^n)与平方底指数型O(2^n)类似,只不过基数变为了3和k 。
O(Math.pow(3, n))O(Math.pow(k, n))假设n为100,假设k为5 。Math.pow(3, n)为5.153775207320113e+47 。Math.pow(5, n)为7.888609052210118e+69 。时间复杂度也是巨高,真的是指数爆炸。
更多的斐波那契数列时间复杂度O(2^N)的分析可以查看下文中的:如何理解斐波那契数列的时间复杂度O(2^N)?
阶乘型O(n!)极其不常见算法消耗随n的增长而增长,性能糟糕function nFacRuntimeFunc(n) {for(let i=0; i<n; i++) {nFacRuntimeFunc(n-1);}}阶乘型O(n!)的时间复杂度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1)+ ··· 的方式去计算 。注意哦,这里是多个阶乘的和 。不仅仅是n * (n-1) * (n-2) * (n-3)···1 。假设n从0到10,它的算法复杂度O(n!)依次为1,4,15,64,325,1956,13699,109600,986409,9864100··· 为了和上文中的其它算法复杂度做比较,n为100时是多少呢? O(2^n)为10才是1024,n为100时O(2^n)直接浏览器卡死了 。O(n!)才为10就接近1000万了,真要是n设置成100,计算到机器烧了也计算不出吧 。所以n为100时的O(n!)就不要想了,庞大到恐怖的一个数字 。
以上关于本文的内容,仅作参考!温馨提示:如遇健康、疾病相关的问题,请您及时就医或请专业人士给予相关指导!
「四川龙网」www.sichuanlong.com小编还为您精选了以下内容,希望对您有所帮助:- 狮子座本周运势综合解析 狮子座今日运势
- 解析气对人体的几大作用
- 蚂蚁庄园金銮殿是故宫的哪个宫殿 1月7日答案解析
- 中医解析气功减肥原理
- 免备案服务器推荐 免费备案域名解析
- 网站域名解析ip方法 网站dns查询方式
- 解析太极拳实战经验
- ip域名解析查询 代理域名备案服务
- 各类游泳动作的要点解析
- 国内DNS测速网站推荐 dns测速在线解析