问题描述
我知道将循环计数器减半的时间复杂度是 log n 。也就是说，如果我们有以下循环：
I know the time complexity when we halve loop counter is log n. That is, if we have following loop:
for(i=1 ; i<n ; i*=2) { ... }
然后时间复杂度变为 log n 。
应该将减半循环计数器 i 再次给出 log log n 时间复杂吗？那是针对下面的循环
Shouldnt halving loop counter i again give log log n time complexity? That is for below loop
for(i=1 ; i<n ; i*=4) { ... }
时间复杂度 log log n 吗？
我尝试了 n 的一些值：
n = 2^8 = 256
i = 1,4,16,64,256 (5 times)
n = 2^10 = 1024
i = 1,4,16,64,256,1024 (6 times)
n = 2^16 = 65536
i = 1,4,16,64,256,1024,4096,16384,65536 (9 times)
似乎循环体为（log n）/ 2-1 次。
我对此分析是否正确，并且两次将循环计数器减半仍然确实给出了 O（log n）时间复杂度而不是 O（log log n）时间复杂度？
it seems that the loop body gets executed for (log n)/2-1 times.Am I correct with this analysis and halving loop counter twice does indeed still gives O(log n) time complexity and not O(log log n) time complexity?
推荐答案
您忘记了基础。在第一种情况下，我们假设基数为2，因此我们将复杂度写为 O（logn）。
You are forgetting the base. In the first case, we assume the base is 2, so we just write the complexity as O(logn).
在第二种情况下，底数应为4，因为我们乘以4，所以它应为 O（log n）。
In the second case, the base should be 4 because the we are multiplying by 4 so it should be O(logn).
这篇关于将循环计数器减半的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！