这个函数的时间复杂度？

Question

algo(n)
   for i in 0 to n {
      for 0 to 8^i {
      }
   }
   for i to 8^d {
   }

有关此算法时间复杂度的任何类型的分析或信息都将很有用。最坏情况、最好情况、lower/upper 边界、theta/omega/big-o、递归关系....等

Answer 1

您的算法以指数时间运行（T ∈ Θ(c^n)、c>1）。您可以使用 Sigma 符号分析内部 for 循环 (... for 0 to 8^i) 的迭代次数：

因为你的算法在Θ(8^n)，它也在O(8^n)（上渐近界）和Ω(8^n)（下渐近界）。

以上分析是在假设最后的for循环分析中的d小于等于n的情况下进行的，此时嵌套的两个for 之前的循环将占主导地位（因此我们不需要明确分析最后一个非主导 for 循环）。

Answer 2

algo(n) 基本上由两部分组成：

   for i in 0 to n
      for 0 to 8^i

和

   for i to 8^d

让我们从第一个开始。假设内循环的每次迭代都需要常数时间，它的复杂度是C*8^i。现在，如果我们对 i 的可能值求和，我们得到：

8^0 + 8^1 + 8^2 + .... + 8^n-1

这是sum of geometric series和a=1, r=8，其总和是：

1 * (1-8 ^(n-1)) / (1-8) = 1 * (-1/7 + 8^(n-1)/7)

对于n->infinity，这可以近似为8^(n-1)/7，我们可以得出复杂度为Θ(8^(n-1)/7) = Θ(8^n)

至于第二部分，它非常简单，是 8^d。

这给出了 T(n) 的总复杂度在 Θ(8^d + 8^n)

中

Time complexity of this function?