各种嵌套for循环的时间复杂性

Question

时间如果循环变量被划分/乘以常量，则循环的复杂性被视为O（Logn）。

环1 ----

for (int i = 1; i <=n; i *= c) 
{ 
    // some O(1) expressions 
} 

环2 -----

for (int i = n; i > 0; i /= c) 
{ 
    // some O(1) expressions 
} 

时间的循环的复杂性被认为是O（LogLogn）如果循环变量被降低/以恒定的数量呈指数增长。

Here c is a constant greater than 1 

环3 ----

for (int i = 2; i <=n; i = pow(i, c)) 
{ 
    // some O(1) expressions 
} 

回路4 -----

////Here fun is sqrt or cuberoot or any other constant root 
for (int i = n; i > 0; i = fun(i)) 
{ 
    // some O(1) expressions 
} 

任何人都可以解释我为什么它是考虑的次数内循环在这些循环中执行？

如果在循环1和循环2中c = 1，那么它将无限次地运行正确，但它是以对数时间给出的原因？

它是如何O（loglogN）在循环3和循环4？

Answer 1

如果在循环1和循环2中c = 1，那么它将无限次地运行正确，但它是以对数时间给出的。

是的，你是对的，如果c = 1那么我们将获得无限循环两种情况1和情况2，因此条件“c是一[整数]常数大于1”还需要两个情况1和情况2，以便获得O(log n)的复杂性。

---

对于情况1，注意i取值1, c, c2, c3, ..., clogc(n)，所以总共有log(n)多次迭代，以及对于每次迭代存在要完成（即O(1)工作的量）的工作的一个恒定量，所以总工作量为log(n) * O(1) = O(log(n))。

类似地，对于壳体2，i取值n, n/c, n/c2, n/c3, ..., , n/clogc(n)，所以总共有log(n)许多迭代和每次迭代花费的时间常数量，所以总的时间复杂度是O(log(n))。

对于情况3,i取值2, 2c, (2c)c = 2c2, (2c2)c = 2c3, ..., 2clogc(log(n))。最后一项必须小于或等于n，我们有2clogc(log(n)) = 2log(n) = n，这证明了我们上一期的价值。所以总共有很多次迭代，每次迭代需要一定的时间，因此总的时间复杂度为O(log(log(n)))。

类似地，对于壳体4，i取值n, n1/c, (n1/c)1/c = n1/c2, n1/c3, ..., n1/clogc(log(n))，所以总共有logc(log(n))迭代和每一次迭代花费时间O(1)，所以总的时间复杂度是O(log(log(n)))。