从品牌网站建设到网络营销策划,从策略到执行的一站式服务
本篇内容介绍了“什么是大O符号”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
专注于为中小企业提供成都网站设计、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业万柏林免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了近千家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。
时间复杂度vs空间复杂度
大O符号用于度量时间复杂度和空间复杂度。
时间复杂度:为完成整体操作而必须执行的小操作的数量。
空间复杂度:运行算法中的代码所需的额外内存量——通常被称为辅助空间复杂度,也就是说它仅指代算法所占用的空间,不包括输入所占用的空间。
复杂度类型
时间复杂度可以分为几种不同的类型。下列是几种较常见类型:
常数阶/O(1):无论数据集多大,始终在相同的时间或空间中执行。
对数阶/O(log n):为获得给定数据,固定数据所必须增加的幂。
线性阶/ O(n):复杂度与输入数据的大小直接相关。
线性对数阶/ O(nlog n):对输入中的每一项执行O(log n)操作。
平方阶/O(n²):性能与输入数据的平方大小成正比。
图源:Colt Steele的JavaScript算法和数据结构大师班
有助于确定时空复杂度的一般规则
这些规则是可以起作用的方向,但不保证每次都有效果。
确定时间复杂度:
算术运算恒定
变量赋值为常数
数组(通过索引)或对象(通过键)中的访问元素是常量
在循环中,复杂度是循环的长度乘以循环内发生的任何事情的复杂度。
确定空间复杂度:
大多数基元是常量空间。(布尔常量,数字,未定义变量,空。)
字符串需要O(n)空间,其中n是字符串的长度。
引用类型通常为O(n),其中n是对象的数组长度或键数。
来看一些例子
图源:Colt Steele的JavaScript算法和数据结构大师班
至于空间复杂度,addUpToN有2个变量赋值(total和i)。当循环完成其操作时,这些变量会被重新分配,但无论输入数据集的大小如何,这些变量占用的空间都保持不变。空间复杂度将为常数阶/O(1)。
这里有3个简单的运算(乘、加、除)。不管n的大小如何,操作的数量保持不变。addUpToNAgain的时间复杂度为常数阶/O(1)。
此时只会返回一个值。输入值不会改变分配给此函数的空间。因此,空间复杂度也是线性阶/O(1)。
在这里,有一个线性阶O(n)运算嵌套在另一个O(n)运算中。当输入的n值缩放时,运行时间随之发生变动。sumEachPair的时间复杂度是平方阶/O(n²)。
回顾一下前文所述的一般规则,这个案例正好对应了其中一条:引用类型一般是O(n),其所需的空间量与输入值直接相关。空间复杂度则为线性阶/O(n)。
想分析算法的性能,可以使用大O符号帮助分析,大O符号可以加深对算法的时间和空间要求的理解。
总之,程序员要理解好所编写的代码的时空复杂度,进而确保运行时间和执行速度达到最快,同时保证代码始终保持在其运行系统的实体存储范围内,“修炼”成一个高效的程序员。
“什么是大O符号”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图