渐近表示法 - n (log n) (log n) 是否简化？

Question

如果我有一个需要 n log n 步骤的算法（例如堆排序），其中步骤需要 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 表示是多少？

Answer 1

这是一个矛盾的证据：

假设函数f（n）= n（log n）（log n）。假设我们认为它也是theta（n log n），所以换句话说，有一个f，其中f（n）<！> lt; = a * n log n适用于大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函数。

Answer 2

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

在特定的应用程序中，大多数情况下，大整数遵循一些特定的分布。例如，可以知道它们都低于10 ^ 20。如果是，则比较操作采用恒定时间（由10 ^ 20的上限确定）。然后，log M也是常数，整个复杂度在O（N log N）。

Answer 3

您将无法将n (log n) (log n)简化为n (log n)，因为这不是一个常数因素的减少。

2 ^<=> ？

出了什么问题

Answer 4

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

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

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

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

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

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

---

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