66.5k
2018-04-11 03:35:33
是的，嵌套循环是一种快速获得大O表示法的方法。
通常（但并非总是如此），一个循环嵌套在另一个循环中会导致O（n²）。
考虑一下，对于i的每个值，内部循环都会执行i次。外循环执行n次。
因此，你会看到这样的执行模式：1 + 2 + 3 + 4 + ... + n次
因此，我们可以说代码执行次数超过n次（下限）来限制代码执行的次数，但是就n而言，我们执行代码多少次？
好吧，在数学上我们可以说它将执行不超过n²次，这给了我们最坏的情况，因此我们的O（n²）的Big-Oh边界。（有关我们如何用数学的眼光看待幂级数的更多信息）
Big-Oh并不总是准确地衡量要完成的工作量，但通常会给出最坏情况的可靠估计。
4年后编辑：因为此帖子似乎获得了大量访问量。我想更全面地说明我们如何使用幂级数将执行绑定到O（n²）
从网站上：1 + 2 + 3 + 4 ... + n =（n²+ n）/ 2 =n²/ 2 + n / 2。那么，如何将其转换为O（n²）？我们（基本上）在说的是n²> =n²/ 2 + n / 2。这是真的？让我们做一些简单的代数。
- 将两侧乘以2得到：2n²> =n²+ n？
- 展开2n²得到：n²+n²> =n²+ n？
- 从两侧减去n²得到：n²> = n？
应该清楚的是，假设n始终是整数，则n²> = n（由于n = 0或1的情况，所以不严格大于n）。
Big O的实际复杂度与我刚才所说的略有不同，但这就是要点。实际上，对于具有足够大的输入量，Big O复杂性询问是否可以将一个常数应用到一个函数，使其大于另一个函数（请参见Wikipedia页面）
热门帖子
热门github
1
2
3
5
6
7
8
11
13
14
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.
(翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
我可以在这里问一个小问题吗？如果“ //某些代码”部分是具有O（N）复杂度的某种计算，结果将如何计算？我认为这是常见的情况，其中一个函数调用另一个函数，并将后面的函数视为具有规范所提供的某些复杂性的黑匣子？
@ ShawnLe：有见地的观察。在大多数假设中，是的，我们假设它
//some code是O（1），因此不会考虑到Big O的复杂性。如果实际上是O（N），那么我们的整体复杂度将变为O（N ^ 3）。将其视为乘法（因为是乘法）。对于〜N个外循环迭代，该内循环迭代〜N次，每次迭代执行〜N个工作。N倍N倍N = N ^ 3。不要忘记堆化是两个嵌套循环（在构建堆时），但是它的O（n）。