用整数将循环计数器除以常数的循环的时间复杂度 [英] Time Complexity of a loop that integer divides the loop counter by a constant

问题描述

我正在尝试以O表示法计算简单算法的时间复杂度，但是其中一部分严重困扰着我。这是该算法的简化版本：

I'm trying to calculate the time complexity of a simple algorithm in big O notation, but one part of it is seriously boggling my mind. Here is a simplified version of the algorithm:

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

在这种情况下，它是整数除法，因此while循环将在a的值降至8以下时终止。我不确定如何用n表示。我还想知道如何处理类似这样的将来的计算，在这些计算中，循环数很难定义。

In this instance, it's integer division, so the while loop will terminate after a's value drops below 8. I'm not sure how to express this in terms of n. I'd also like to know how to tackle future calculations like this, where the number of loops isn't too easy to define.

推荐答案

在这样的情况下，我发现以其他方式进行操作更容易。与您正在做的事情（甚至是近似）有什么相反？

I find it easier to do it the other way around in cases like this. What is the opposite of what you're doing (even approximately)? Something like:

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

现在，我们更改了同时换为 ，它具有固定的步数，并且可以递减到增量，这样更容易使用。

Now, we've changed the while to a for, which has a fixed number of steps, and decrementation to incrementation, which can be easier to work with.

我们有：

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）。

So your while loop executes O(log n) times. If you have something that is O(n^3) inside, then your entire sequence will be O(n^3 log n).

这篇关于用整数将循环计数器除以常数的循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！