什么是大O符号

本篇内容介绍了“什么是大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符号”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！