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。

另一种选择是编写一个递归函数，其运行时间通过主定理计算为 O(n ³ log n)。一种方法是使用一个函数，对大小为 n / 2 的子问题进行 8 次递归调用，并且每次调用都工作Θ(n ^{3 )：}

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 ³的数组进行排序来获得运行时 O(n ^{3 log n)。更一般地，在大小为 n 3}的输入上运行运行时间为 O(n log n) 的任何算法都会产生 O(n ³ log n) 的运行时间。这使用了 log (n ³ ) = 3 log n = O(log n) 的事实。

希望这可以帮助！

Answer 2

您可以使用代数向后解决这个问题。

递归 T(n^3/3) 算法给你 O(n^3)，所以现在你只需要一个 T(n/2) 来记录日志。

N 必须等于 K 才能工作

过程 T(n,k) 是

T(n^3/3,k) 如果 n >=0

T(n,k/2) 如果 k>=0 且 n<=0

它将运行 O(n^3)，然后是 O(log n)，因此无论如何，该程序的最小运行时间是 O(n^3 log n)

我如何获得 T 函数的值？让我们从求解 T(n/2) 开始。

T(n)=T(n/2)+1。加 1 是我们完成递归后基本操作需要多长时间。T(n/2) = T(n/4) + 1 因此 T(n) = T(n/4) + 2

我们可以推断出 T(n) = T(n/2^k) + k。

T(1) 是我们的基本情况，所以让 n/2^k 等于 1 并求解 k。

K = log n（以 2 为底）

所以这意味着这个函数有 O(log n) 的大 O。

可以对 T(n^3/3) 进行相同的数学运算。

让我知道这是否没有任何意义。