问题标签 [time-complexity]

找出 JavaScript 数组是否包含值的最简洁有效的方法是什么？

这是我知道的唯一方法：

有没有更好更简洁的方法来实现这一点？

时间复杂度是多少？为什么？

^{给定一个长度为 2 32}的 32 位无符号整数数组，对于某些 32 位无符号整数 N，该数组中超过一半的条目等于 N。查找 N 查看每个数字在数组中只使用一次，最多使用 2 kB 的内存。

您的解决方案必须是确定性的，并保证找到 N。

使用new、malloc等动态内存分配的时间复杂度是多少？我对如何实现内存分配器知之甚少，但我认为答案是它取决于实现。因此，请回答一些更常见的案例/实现。

编辑：我隐约记得听说堆分配在最坏的情况下是无限的，但我对平均/典型情况真的很感兴趣。

我了解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直试图弄清楚斐波那契数列的原始版本的计算复杂性：

斐波那契数列的计算复杂度是多少，它是如何计算的？

好吧，我有这段代码大大减慢了程序的速度，因为它是线性复杂度，但被调用了很多次，使程序成为二次复杂度。如果可能的话，我想降低它的计算复杂度，否则我会尽可能地优化它。到目前为止，我已经减少到：

有人看到我错过的任何东西吗？谢谢！

编辑：我忘了提：n 总是一个素数。

编辑 2：这是我的新改进程序（感谢所有贡献！）：

编辑 3：在真实环境中测试它要快得多！好吧，这个问题似乎已解决，但有很多有用的答案。我还应该说，除了上述优化之外，我还使用 Python 字典记住了该函数......

有时我看到 Θ(n) 带有奇怪的 Θ 符号，中间有东西，有时只是 O(n)。只是懒惰打字，因为没有人知道如何输入这个符号，还是意味着不同的东西？

是否存在一种广泛使用的算法，其时间复杂度比另一种已知算法差，但在所有实际情况下它都是更好的选择（复杂度更差，但其他情况更好）？

可接受的答案可能是以下形式：

有一些算法具有相应的时间复杂度，但是A具有如此大的常数，以至于对于少于宇宙中原子数量的输入 ，它没有任何优势。BO(N**2)O(N)BA

答案中的示例突出显示：

• 单纯形算法——最坏的情况是指数时间——与用于凸优化问题的已知多项式时间算法相比。

• 中位数算法的天真中位数 - 最坏情况 O(N**2)与已知 O(N) 算法。

• 回溯正则表达式引擎——最坏情况指数与O(N) 基于 Thompson NFA 的引擎。

所有这些示例都利用了最坏情况与平均情况。

是否有不依赖于最坏情况与平均情况之间差异的示例？

有关的：

• “越差越好”的兴起。（为了这个问题的目的，“Worse is Better”短语的使用范围比文章中的更窄（即算法时间复杂度））

• Python的设计理念：

  ABC集团力求完美。例如，他们使用了基于树的数据结构算法，这些算法已被证明对于渐近大型集合是最佳的（但对于小型集合来说并不是那么好）。

  如果没有计算机能够存储这些大型集合（换句话说，在这种情况下大不够大），这个例子就是答案。

• 用于方阵乘法的Coppersmith–Winograd 算法是一个很好的例子（它是最快的（2008 年），但不如更差的算法）。还有其他人吗？ 来自维基百科的文章：“它没有在实践中使用，因为它只为大到现代硬件无法处理的矩阵提供优势（Robinson 2005）。”

好的，这不是“如何获取所有唯一性”或“如何在 php 中从我的数组中删除重复项”的问题。这是一个关于时间复杂度的问题。

我认为array_unique有点 O(n^2 - n) ，这是我的实现：

但是，当对此进行基准测试时，array_unique我得到了以下结果：

测试 (array_unique2)... 操作耗时 0.52146291732788 秒。

测试 (array_unique)... 操作耗时 0.28323101997375 秒。

这使得 array_unique 快两倍，我的问题是，为什么（两者都有相同的随机数据）？

我的一个朋友写道：

这比 php.ini 中内置的快一倍。

我想知道，为什么？

array_unique 和 in_array 的时间复杂度是多少？

编辑 我从两个循环中删除了 count($array) 并在函数顶部使用了一个变量，它在 100 000 个元素上获得了 2 秒！

我更喜欢尽可能少的正式定义和简单的数学。