摘要:第三段,时间复杂度。五空间复杂度分析空间复杂度的话和时间复杂度类似推算。
一、前言
时间复杂度和空间复杂度,我们在大学里的算法与数据结构课程中已经学习过,这回根据项目工作中整理一下,这个估计只是一个粗略的估计分析,并不是一个准确的估计分析。
1、学习时间复杂度和空间复杂度是很有必要的,这个属于算法与数据结构的范畴,学这个是为了解决代码中的“快”和“省”的问题。这样才能使你的代码运行效率更高,占用空间更小。代码执行效率需要通过复杂度分析。
2、数据规模的大小会影响到复杂度分析。比如排序,如果是一个有序的数组,执行效率会更高;如果数据量很少的时候,这个算法看不出性能上差别。
3、比如说不同物理机环境不一样,比如i3,i5,i7的cpu等等,运行内存1G,2G,4G,8G等等;时间上肯定有差别。
二、大O的复杂度我们来看个简单的例子,一个循环累加器。
function total(n) { var sum = 0; //t for (var i = 0; i < n; i++) { // nt sum += i; //nt } return sum; // t }
分析:假设每一行代码执行耗时都一样,为t,这样整个代码总执行时间为(t+nt+nt+t)=(2n+2)t。
我们再来看一个栗子:
function total(n) { var sum = 0; // t for (var i = 0; i < n; i++) { //nt for (var j = 0; j < n; j++) { //n*n*t sum = sum + i + j; //n*n*t } } return sum; //t }
分析:假设每一行代码执行耗时都一样,为t,这样整个代码总执行时间为(t+nt+nnt2+t)=(2nn+n+2)t。
从数学角度来看,我们可以得出个规律:代码的总执行时间 T(n) 与每行代码的执行次数成正比.
所以上边两个函数的执行时间可以标记为 T(n) = O(2n+2) 和 T(n) = O(2n*n+n+2)。这就是大 O 时间复杂度表示法,它不代表代码真正的执行时间,而是表示代码随数据规模增长的变化趋势,简称时间复杂度。
而且当 n 很大时,我们可以忽略常数项,只保留一个最大量级即可。所以上边的代码执行时间可以简单标记为 T(n) = O(n) 和 T(n) = O(n2)。
三、时间复杂度分析 1、循环次数最多的代码块在分析的时候,只需要关心哪个代码块循环次数最多的那段代码,比如说刚才的第一个例子,循环最多的代码块是这两行,循环都是n次。
for (var i = 0; i < n; i++){ sum += i; }
执行了n次,所以事件复杂度就是O(n)。
2、最大值原则:总复杂度等于最大的代码块的复杂度function total(n) { // 第一个 for 循环 var sum1 = 0; for (var i = 0; i < n; i++) { for (var j = 0; j < n; j++) { sum1 = sum1 + i + j; } } // 第二个 for 循环 var sum2 = 0; for(var i=0;i<1000;i++) { sum2 = sum2 + i; } // 第三个 for 循环 var sum3 = 0; for (var i = 0; i < n; i++) { sum3 = sum3 + i; } return {sum1:sum1, sum2: sum2, sum3:sum3} }
分别分析每一段循环时间复杂度,取他们最大的量级决定整段代码复杂度。
第一段,时间复杂度 O(n2)。
第二段,时间复杂度可以忽略,循环执行了 1000 次,是个常数量级,尽管对代码的执行时间会有影响,但是当 n 无限大的时候,就可以忽略。
第三段,时间复杂度O(n)。
综上所述,所以上述代码的时间复杂度为 O(n2)。
3、乘法原则:嵌套代码复杂度等于嵌套内外代码复杂度乘积举个例子:
function f(i) { var sum = 0; for (var j = 0; j < i; j++) { sum += i; } return sum; } function total(n) { var res = 0; for (var i = 0; i < n; i++) { res = res + f(i); // 调用 f 函数 } }
分析一下:total方法时间复杂度O(n),f方法的时间复杂度O(n)。
所以整段代码的时间复杂度O(n2)。
四、常见的时间复杂度分析最高量级的复杂度,效率是递减的
如上图可以粗略的分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个:O(2n) 和 O(n!) 对应的增长率如下图所示
当数据规模 n 增长时,非多项式量级的执行时间就会急剧增加,所以,非多项式量级的代码算法是非常低效的算法。
1、常数阶复杂度O(1)O(1) 只是常量级时间复杂度表示法,并不是代码只有一行,举个例子:
function total() { var sum = 0; for(var i=0;i<100;i++) { sum += i; } return sum; }
虽然有这么多行,即使 for 循环执行了 100 次,但是代码的执行时间不随 n 的增大而增长,所以这样的代码复杂度就为 O(1)。
2、对数阶O(logn)和O(nlogn)(1)对数阶时间复杂度的常见代码如下:
function total1(n) { var sum = 0; var i = 1; while (i <= n) { sum += i; i = i * 2; } } function total2(n) { var sum = 0; for (var i = 1; i <= n; i = i * 2) { sum += i; } }
上面函数total1和total2有一个相同点:变量 i 从 1 开始取值,每循环一次乘以 2,当大于 n 时,循环结束。
所以真正循环了x次。2x =n;,所以 x = log2n。
所以上面两个函数时间复杂度都是 O(log2n)。
(2)我们在举个例子:
function total1(n) { var sum = 0; var i = 1; while (i <= n) { sum += i; i = i * 3; } } function total2(n) { var sum = 0; for (var i = 1; i <= n; i = i * 3) { sum += i; } }
同理可知:这两个函数的时间复杂度为 O(log3n) 。
由于我们可以忽略常数,也可以忽略对数中的底数,所以在对数阶复杂度中,统一表示为 O(logn);那 O(nlogn) 的含义就很明确了,时间复杂度 为O(logn) 的代码执行了 n 次。
3、其他复杂度O(m+n)和O(m*n)举个例子:
function total(m,n) { var sum1 = 0; for (var i = 0; i < n; i++) { sum1 += i; } var sum2 = 0; for (var i = 0; i < m; i++) { sum2 += i; } return sum1 + sum2; }
因为我们无法评估 m 和 n 谁的量级比较大,所以就不能忽略掉其中一个,这个函数的复杂度是有两个数据的量级来决定的,所以此函数的时间复杂度为 O(m+n);那么 O(m*n) 的时间复杂度类似。
五、空间复杂度分析空间复杂度的话和时间复杂度类似推算。 所谓空间复杂度就是表示算法的存储空间和数据规模之间的关系。
举个例子:
function initArr(n) { var arr = []; for (var i = 0; i < n; i++) { arr[i] = i; } }
时间复杂度的推算,忽略掉常数量级,每次数组赋值都会申请一个空间存储变量,所以此函数的空间复杂度为 O(n)。
常见的空间复杂度只有 O(1)、O(n)、O(n2)。其他的话很少会用到。
六、复杂度优化function total(n) { var sum = 0; for (var i = 1; i <= n; i++) { sum += i; } return sum; }
这段代码我们很容易知道时间复杂度 O(n)。
但是我想把复杂度降一降,降低到常数阶O(1)。
其实求和怎么求呢?等比数列,直接用公式,这就说明了数学好的人,算法应该高level点。
function total(n) { var sum = n*(n+1)/2 return sum; }
上面函数的时间复杂度仅仅为 O(1),在数据规模比较庞大的时候,下面的函数是不是明显比上面的函数运算效率更高呢。
七、总结分析算法执行效率与数据规模之间的增长关系,可以粗略的表示,越高阶复杂度的算法,执行效率越低。
复杂度学习之后,有时候可以避免写出效率低的代码。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/105934.html
摘要:散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中,我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现,利用递归和广度优先搜索的思想实现。 什么是广度优先搜索? 如果只是是背概念,幼儿园的小朋友都能背下来念给你听。 假设看这篇文章的都和我一样是个前端工程师,我们要从广度优先搜索(BFS)中学到什么...
摘要:也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。如果对象没有该实例化该处为一对象如果该不存在就增加一个数量 本系列一系列文章的收集关于javascript中的数据结构 如果你对数据结构不太熟悉 可以看这篇文章如果你只想看代码 可以看这篇文章如果你只想star 可以去这里 什么是数...
摘要:之所以把计数排序桶排序基数排序放在一起比较,是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位,范围太大,显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者...
摘要:小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路,第一利用递归第二利用动态规划。就是因为有了重复元素的计算,导致了时间复杂度成指数的增长。 Time:2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 题目:Climbing Stairs You a...
阅读 2376·2021-09-30 09:47
阅读 1367·2021-09-28 09:35
阅读 3237·2021-09-22 15:57
阅读 2485·2021-09-22 14:59
阅读 3634·2021-09-07 10:25
阅读 3069·2021-09-03 10:48
阅读 3035·2021-08-26 14:14
阅读 933·2019-08-30 15:55