我试图计算一个简单的算法在大O符号的时间复杂度，但它的一部分严重困扰我的头脑。以下是算法的简化版本：
int a=n
while(a>0)
{
//for loop with time complexity n^3
a = a/8
}
在本例中，它是整数除法，因此while循环将在a的值降到8以下后终止。我不知道如何用n来表示，我也想知道如何处理这样的未来计算，循环的数量不太容易定义。
最佳答案
我发现在这种情况下，用另一种方法做起来更容易。与你正在做的事情相反（甚至差不多）？类似于：
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)。