algorithm - 提供一个操作简单的算法O(n^3 log n)？

Question

提供一个算法计算性能O(n³ log n)。该算法应该只包含简单的操作。

知道如何解决这个问题吗？...我正在攻读计算机科学 GRE。谢谢!

Answer 1

一种方法是编写一个运行 O(n³) 次的外循环和一个运行 O(log n) 次的内循环:

for (int i = 0; i < n * n * n; i++) {
   for (int j = 1; j <= n; j *= 2) {
       // ... do nothing ... //
   }
}

请注意，内部循环运行 log n 次，因为循环 k 次迭代后 j 的值为 2^k，一旦 k ≥ lg n，我们将得到 j = 2 ^k ≥ n.

另一种选择是编写一个递归函数，其运行时通过 Master Theorem ，计算出 O(n³ log n)。一种方法是使用一个函数，该函数对大小为 n/2 的子问题进行 8 次递归调用，并且每次调用执行 Θ(n³) :

void silly(int n) {
    if (n > 0) {
        for (int i = 0; i < n * n * n; i++) {
            // ... waste time ... //
        }
        for (int i = 0; i < 8; i++) {
            silly(n / 2);
        }
    }
}

编辑:正如@Nuclearman 指出的那样，您还可以通过对大小为 n³³ log n) sup> 使用像快速排序或堆排序这样的算法。更一般地说，在大小为 n³ 的输入上运行运行时间为 O(n log n) 的任何算法都会产生 O(n³ log n) 的运行时间。这使用了 log (n³) = 3 log n = O(log n) 的事实。

希望这对您有所帮助!