algorithm - 整数除以循环计数器除以常数的循环的时间复杂度

Question

我正在尝试用大 O 表示法计算一个简单算法的时间复杂度，但其中一部分让我非常困惑。这是该算法的简化版本:

int a=n
while(a>0)
{
//for loop with time complexity n^3
a = a/8
}

在这个例子中，它是整数除法，所以 while 循环将在 a 的值低于 8 后终止。我不确定如何用 n 来表达这个。我还想知道如何处理像这样的 future 计算，其中循环的数量不太容易定义。

Answer 1

在这种情况下，我发现反过来更容易。与您正在做的事情(甚至近似)相反的是什么？像这样的东西:

for (a = 1; a <= n; a = a * 8)
{
    ...
}

现在，我们已将 while 更改为 for，它具有固定的步数，并且从递减到递增，这样更易​​于使用。

我们有:

1, 8, 8^2, ..., 8^k <= n

8^k <= n | apply logarithm

log (8^k) <= log n

k log 8 <= log n

=> k = O(log n)

因此您的 while 循环执行了 O(log n) 次。如果您的内部有 O(n^3) 的内容，那么您的整个序列将是 O(n^3 log n)。