big-o - 为这段代码建立一个递归关系？

Question

我需要为以下算法建立一个递归关系（T（n）代表元素动作的数量）并找到它的时间复杂度：

Alg (n)
{
    if (n < 3) return;
    for i=1 to n
    {
       for j=i to 2i
       {
           for k=j-i to j-i+100
              write (i, j, k);
       }
    }

    for i=1 to 7
       Alg(n-2);
 }

我来到了这个 Recurrence 关系（不知道对不对）：

如果 n < 3，则 T(n) = 1

T(n) = 7T(n-2)+100n ²否则。

不过，我不知道如何获得时间复杂度。

我的复发正确吗？这段代码的时间复杂度是多少？

Answer 1

让我们看一下代码，看看递归应该是什么。

首先，让我们看一下循环：

    for i=1 to n
    {
       for j=i to 2i
       { 
           for k=j-i to j-i+100
               write (i, j, k);
       }
    }

这做了多少工作？好吧，让我们从简化它开始。让我们定义一个从to向上计数的新变量，而不是j从to计数。这意味着= ，所以我们得到这个：i2ij'0ij'j - i

    for i=1 to n
    {
       for j' = 0 to i
       { 
           for k=j' to j'+100
               write (i, j' + i, k);
       }
    }

啊，这样好多了！现在，我们也重写k为k'，k'范围从 1 到 100：

    for i=1 to n
    {
       for j' = 0 to i
       { 
           for k'= 1 to 100
               write (i, j' + i, k' + j);
       }
    }

由此，更容易看出这个循环的时间复杂度为 Θ(n ² )，因为最里面的循环做了 O(1) 的工作，而中间的循环将运行 1 + 2 + 3 + 4 + ... + n = Θ(n ² ) 次。请注意，它不完全是 100n ²，因为总和不完全是 n ²，但它很接近。

现在，让我们看一下递归部分：

for i=1 to 7
    Alg(n-2);

对于初学者来说，这简直是愚蠢的！你没有理由想要做这样的事情。但是，也就是说，我们可以说这是对大小为 n - 2 的输入的算法的 7 次调用。

因此，我们得到这个递归关系：

T(n) = 7T(n - 2) + Θ(n ² ) [如果 n ≥ 3]

T(n) = Θ(1) [否则]

现在我们有了递归，我们可以开始计算时间复杂度。这最终有点棘手。如果你想想我们最终会做多少工作，我们会得到的

• 有 1 个大小为 n 的调用。
• 有 7 个大小为 n - 2 的调用。
• 有 49 个大小为 n - 4 的调用。
• 有 343 个大小为 n - 6 的调用。
• ...
• 有 7 ^k个大小为 n - 2k 的调用

^{由此，我们立即得到 Ω(7 n/2} )的下限，因为这是将要进行的调用次数。每次调用都会 O(n ² ) 工作，因此我们可以获得 O(n ² 7 ^n/2 ) 的上限。真正的价值就在那里，虽然老实说我不知道​​如何弄清楚它是什么。对于那个很抱歉！

希望这可以帮助！

Answer 2

正式的方法是执行以下操作：

当涉及到递归调用的数量时，可以从源代码中直观地推断出主要的增长顺序。

具有 2 个递归调用的算法的复杂度为 2^n；3 次递归调用的复杂度为 3^n，依此类推。