我有一个猜测，但我不确定。
这就是问题所在。
for (a = 1 ; a<n ; a= 2*a) do {
for (b=n; b > 0; b=b-a) do {
}
}
这是我在stackoverflow上的第一个问题 所以我希望我的格式是正确的。
非常感谢您。
对于大O符号的推理，有一个有用的格言，是这样的。
当有疑问的时候，从内到外的工作！
更具体地说，如果你想弄清楚一个循环嵌套的复杂程度，就从最里面的循环开始，然后不断地用一个更简单的语句来代替它，总结所做的工作量。
在你的案例中，你有这些循环。
for (a = 1 ; a<n ; a= 2*a) do {
for (b=n; b > 0; b=b-a) do {
}
}
我们从最里面的循环开始
for (b=n; b > 0; b=b-a) do {
}
这个循环要运行多少次？那么，我们从 b 与...相当 n，每次迭代时 b 减少了 a. 这意味着这个循环的迭代次数大约是 n a，所以这个循环的复杂度是Θ(n a)。因此，我们可以用 "做Θ(n a)的工作 "这样的话来代替内部循环，得到这个更简单的结构。
for (a = 1 ; a<n ; a= 2*a) do {
do Θ(n / a) work;
}
现在，让我们想想这个循环做了多少工作。由于循环内部所做的工作量取决于以下的值 a我们不打算将迭代次数乘以每次迭代所做的工作，因为每次迭代所做的工作不是一个常数。取而代之的是，我们将把循环的每次迭代所做的工作加起来。
请注意，a 的值随着 1、2、4、8、16、32......的增加而增加，直到我们超额完成 n。将这些值插入循环内部所做的工作，得到的运行时间为
Θ(n 1 + n 2 + n 4 + n 8 + n 16 + ...)
= n Θ(11 + 12 + 14 + 18 + 116 + ...)
你可能认识到，11 + 12 + 14 + 18 + ...之和恰好收敛为2。 (你明白为什么吗？)结果，我们有这个代码的运行时间是
n Θ(2)
= Θ(n)。
所以，这里所做的总体工作是 Θ(n).
我们用来确定的主要技术有以下几点。
希望对大家有所帮助!