Nlogn和其他Big O符号详解

创作时间:

作者:

@小白创作中心

Nlogn和其他Big O符号详解

引用

来源

https://builtin.com/software-engineering-perspectives/nlogn

Big O符号是计算机科学中用于根据算法的时间和空间复杂度对其进行分类的度量。这里的时间和空间不是基于实际执行的操作数量或使用的内存数量，而是基于算法随着输入数据量的增加或减少如何扩展。

什么是Big O符号？

Big O符号是计算机科学中用于根据算法的时间和空间复杂度对其进行分类的度量。它被写为O(x)，并基于算法随着输入数据量的增加或减少如何扩展。Big O符号通常表示算法在最坏情况下的运行方式，换句话说，算法可能使用的时间或空间的最大值。复杂度可以写为O(x)，其中x是算法相对于n的增长率，n是输入数据的数量。在本文的其余部分中，输入将被称为n。

所有Big O符号的复杂度图表。| 图片来源：维基百科

Big O符号的类型

有七种常见的Big O符号。这些包括：

O(1)：常数复杂度
O(logn)：对数复杂度
O(n)：线性复杂度
O(nlogn)：对数线性复杂度
O(n^x)：多项式复杂度
O(X^n)：指数时间
O(n!)：阶乘复杂度

让我们逐一了解它们。

O(1)：常数复杂度

O(1)被称为常数复杂度。这意味着算法的时间或空间复杂度保持不变，无论输入大小n如何，时间或内存的使用量都不会随n扩展。对于时间复杂度，这意味着n不会被迭代或递归。通常，会选择一个值并返回，或者对一个值进行操作并返回。

对于空间，不允许创建数据结构，其大小是n的倍数，因为空间使用量不会随输入大小的增加而增加。可以声明变量，但数量必须不随n变化。

O(logn)：对数复杂度

O(logn)被称为对数复杂度。O(logn)中的对数通常以2为底。理解这一点的最好方法是记住“减半”的概念。每次n增加k时，时间或空间增加k/2。有许多常见的算法大部分时间都是O(logn)，包括二分查找、在二叉搜索树中查找一个词以及向堆中添加项目。

O(logn)空间复杂度通常发生在递归算法中，其中递归深度是对数的（如二分查找）。当进行递归调用时，所有当前变量都会被放置在堆栈上，并创建新的变量。如果递归调用的数量呈对数增长，即每次递归调用时n减半，那么空间复杂度将是O(logn)。O(logn)的空间复杂度很少见。

O(n)：线性复杂度

O(n)，或线性复杂度，可能是最容易理解的复杂度。O(n)意味着时间/空间与n的大小变化成正比。如果每次n增加1时都需要执行一个新操作或迭代，那么算法将以O(n)时间运行。

O(nlogn)：对数线性复杂度

O(nlogn)被称为对数线性复杂度。O(nlogn)意味着logn操作将发生n次。换句话说，对于n个元素中的每一个，都会执行一个对数操作。O(nlogn)时间常见于递归排序算法、二叉树排序算法和大多数其他类型的排序。

O(n^x)：多项式复杂度

O(n^x)，或多项式复杂度，根据x的值覆盖了一大范围的复杂度。x表示每次处理n的所有元素的次数。多项式复杂度是我们进入危险区域的地方。它非常低效，虽然创建某些算法的唯一方法是使用多项式复杂度，但多项式复杂度应该被视为代码可以重构的“警告信号”。这不仅适用于多项式复杂度，也适用于我们将要讨论的所有后续复杂度。

O(X^n)：指数时间

O(X^n)，被称为指数时间，意味着时间或空间将被提升到n的幂。指数时间非常低效，除非绝对必要，否则应避免使用。通常，O(X^n)的结果来自具有X个算法的递归算法，其中每个算法都调用n-1。汉诺塔是一个著名的具有运行在O(2^n)的递归解决方案的问题。

O(n!)：阶乘复杂度

O(n!)，或阶乘复杂度，是存在的“最坏”的标准复杂度。为了说明阶乘解决方案增长速度有多快，一副标准扑克牌有52张牌，洗牌后有52!种可能的顺序。这个数字比地球上的原子数量还要大。如果有人从宇宙开始到现在每秒洗一次牌，他们也不会遇到一副扑克牌的所有可能顺序。可以说：阶乘复杂度是难以想象的低效。

为什么了解Big O符号很重要

前四种复杂度，以及在某种程度上第五种，O(1)、O(logn)、O(n)、O(nlogn)和O(n^x)，可以用来描述你将遇到的绝大多数算法。最后两种将极其罕见，但了解它们对于理解Big O符号的整体概念及其用途非常重要。还有其他一些较小的复杂度存在，例如双重对数(O(loglogn))和分数幂(O(n^x) 0 < x < 1)等，但这些有点小众，不会适用于大多数算法。