1

如果我有一个算法需要 n log n 步骤（例如 heapsort），其中步骤需要 log n 时间（例如比较/交换 0 到 n-1 范围内的“大”整数），那么整个过程。

显然我们可以说“n (log n) (log n)”，但我很难说服自己我不能将其简化为“n log n”。与此同时，我很难证明坚持认为我可以做到的本能。

我的直觉是完全错误的吗？

编辑

似乎我的简单示例避免使问题复杂化使问题复杂化。那好吧。

这个问题的真正原因是我经常有一个已知复杂度的标准算法，但使用不同的底层容器实现，因此各个步骤是 O(log n) 而不是 O(1)。例如，Hopcrofts 自动机最小化算法是 O(n log n) - 但是如果您开始使用二叉树容器来存储状态、转换和中间结果，那么步骤本身就会变成 O(log n) - O(n log n) 是不再有效，因为 O(1) 访问的假设是无效的。

尽管如此，人们仍会声称存在 n 个状态和 m 个转换，但是对于自动机，n 和 m 往往是线性相关的，假设转换注释的数量是恒定的并且自动机或多或少是确定性的。

过去我并没有太担心这一点——我处理的案例并不是很大。但是，好吧，我正在对我的自动机代码进行重大重构，我想我不妨在我进行时对一些关键算法进行正确的数学运算。

编辑

我也越来越相信“n (log n) (log n)”是错误的。

如果 a 是 O(b log b)，而 b 是 O(log c)，那么 a 与 c 的关系是多少？

4

4 回答 4

5

通常，您不能像这样将复杂性相乘：对于堆排序，N 表示堆中的项目数，而对于大整数，N 可能表示可能值的上限。通常，这些不必相关，因此它相当 N log N log M（其中 M 是项目可能采用的范围）。

在特定应用中，大整数很可能遵循某种特定分布。例如，可能知道它们都低于 10^20。如果是这样，比较操作需要固定时间（由上限 10^20 确定）。那么，log M 也是常数，整个复杂度在 O(N log N) 中。

于 2009-10-25T05:40:09.700 回答
3

下面是一个反证法：

假设一个函数f(n) = n(log n)(log n)。假设我们认为它也是Θ(n log n), theta(n log n)，所以换句话说，有一个afor whichf(n) <= a * n log n对 large 成立n。

现在考虑f(2^(a+1))：

f(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * log(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * (a+1)，显然大于a * 2^(a+1) * log(2^(a+1))，我们有一个矛盾。因此f(n)不是n log n函数。

于 2009-10-25T05:54:28.080 回答
2

你不能简单地减少n (log n) (log n)到，n (log n)因为这不是一个常数因子的减少。

有什么问题n (log n)2？

于 2009-10-25T05:37:18.333 回答
1

好的，程序的一般复杂性度量如下：

复杂度 O(f(n)) 意味着存在c，使得相应的图灵机步数在其终止之前不超过 c*f(n)，其中 n 是输入的长度。

在这个定义中，一切都被考虑在内，因为整数可能是任意大的，对它们的算术运算也会增加 O(n) 下的函数。

但是，如果我们直接对图灵机进行编程，就不会出现您的问题。在现实世界中，我们更喜欢抽象。虽然我们仍然计算运行程序所需的“步骤”，但我们假设某些操作需要一步。我们假设由于不同的原因：

  • 它可能类似于 CPU 的实际工作，其中每个 32 位整数加法确实是一个步骤（并且存在实际上滥用它的算法，例如“bit-verctor dominators”）。
  • 我们比较同一域中的不同算法（例如，通过测量比较次数来比较数组排序）。

在这种情况下（您的第一次编辑），如果您想具体化您的复杂性度量，您应该只将 O 下的函数相乘。如果您认为采取的一步现在考虑采取 O(log N) 步骤，那么具体化的数量步数增加了 O(log N) 倍。因此总复杂度为 O(N log N log N)。

至于你的第二次编辑，情况就不同了。让你的算法复杂度为 O(n log N)。但是你知道输入由M数字组成，每个log K数字，所以 `N = O(M log K) （我们需要考虑分隔符等）。将整体复杂度写成 O(M * log K * (log M + log log K)) 在数学上是正确的，所以这里没有问题。但是通常我们会抽象掉不必要的细节，以便为不同的算法找到一个共同的基础进行比较。

于 2009-10-25T07:47:45.950 回答