运行时间为 O(n^2 log n) 的算法示例？

Question

我必须构造一个算法，其上限为 O(n ² log n)。^{谁能提供有关 O(n 2} log n) 算法的示例吗？我似乎无法全神贯注于它。

我对它的想象是两个嵌套的 for 循环，在第二个循环中执行 log n 操作。它是否正确？

Answer 1

有很多方法可以在算法中获得 O(n ^{2 log n) 的运行时间。}这是一个采样器。

\n

\n
• ^{对 n 2 个}项目的列表进行有效排序。例如，如果您获取 n 个项目，形成这些项目的所有 n ²对，然后使用堆排序之类的方法对它们进行排序，则运行时间将为 O(n ² log n ² ) = O(n ² log n)。这源自对数的性质：log n ² = 2 log n = O(log n)。^{更一般地，对大小为 n 2}的输入运行 O(n log n) 时间算法将为您提供 O(n ² log n) 运行时间。
\n
• 使用二元堆在密集图上运行 Dijkstra 算法。Dijkstra 算法在具有 n 个节点和 m 个边的图上（使用二元堆）的运行时间为 O(m log n)。稠密图是 m = \xce\x98(n ² ) 的图，因此在这种情况下，Dijkstra 算法将花费 O(n ² log n) 时间。这也是在密集图上运行其他一些图算法的时间限制，例如使用二元堆时的 Prim 算法。
\n
• 某些分治算法。递推式为 T(n) = 2T(n / \xe2\x88\x9a2) + O(n ² ) 的分而治之算法的运行时间为 O(n ² log n)。例如，这作为 Karger-Stein 最小割算法中的子例程出现。
\n
• 对 n 个项目的二叉树执行 n ^2搜索。每次搜索的成本为 O(log n)，因此总工作量为 O(n ² log n)。更一般地说，执行任何 O(log n) 时间操作总共 O(n ² ) 次就会得到这个界限。
\n
• 后缀数组的简单构造。后缀数组是字符串的所有后缀按排序顺序组成的数组。对后缀进行简单排序需要 O(n log n) 次比较，但由于比较两个后缀可能需要 O(n) 时间，因此总成本为 O(n ² log n)。
\n
• 构建二维范围树。范围树数据结构允许快速查询轴对齐框中 kD 空间中的所有点。在二维中，构造时间为 O(n ² log n)，尽管可以使用一些更聪明的技术将其改进为 O(n log n)。
\n

\n

当然，这不是一个全面的列表，但它给出了实践中 O(n ² log n) 运行时间弹出的采样器。

\n