algorithm - 具有特定运行时 Theta(...) 的递归函数

Question

我被我从算法课程中得到的这个作业困住了：

编写一个运行时间为 Theta(n^4 logn) 的递归函数。

我想过这样的事情，但我对我的方法非常不确定。

function(int n)
{
   for-loop (1..n^4)
     //do something

   return function(n/2);
}

Answer 1

您应该不确定，您的功能有一些问题：

1. 它没有初始值，并且永远运行。

2. 如果您为函数设置初始值，它将为：

   T(n) = T(n/2) + O(n^4)

根据主定理，这是 Θ(n^4)。

提示：你应该增加 的系数T(n/2)，但要增加多少？自己找。对于这种增加，您可以称其为x次。

---

log n当我们有这样的递归时，Master theorem就会发生：

T(n) = a T(n/b) + n ^a/b

在您的情况下，您有 a/b = 4，因此您可以修复 b = 2 和 a = 8 来实现这一点。

T(n) = 8T(n/2) + n ⁴

为了达到这个目的，您可以调用 T(n/2) 8 次。

Answer 2

提示：n ⁴可以是从 1 到 n 的四个嵌套循环。对数运行时间因子通常是通过将问题大小递归减半直到达到 1 来获得的。你的提议有点工作，但是很生硬，你甚至可以这样做

func(int n)
  for i = 1 to n^4 log n
     nop()

但我不相信这是正在寻找的东西。

Answer 3

你的方法是理智的，你的不安全感是正常的。您现在应该证明您的算法是 Theta(n^4 log n)。应用您的常规算法分析技术来显示function执行do somethingn^4 log_2 n 次。

提示：计算function递归调用的次数以及循环在每次调用中运行的频率。您会看到您的函数中仍然存在一个小错误；n每次递归调用中的因子n^4都会减少。