各种嵌套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 那么它将运行无限次正确但它以对数时间给出，为什么？

循环3和循环4的O(loglogN)如何？

Answer 1

If c=1 in loop 1 and loop 2 then it will run infinite times right but it is given as logarithimic time why?

是的，你是对的，如果 c = 1 那么情况 1 和情况 2 都会出现无限循环，所以条件“c 是一个 [n 整数]为了获得 O(log n) 复杂度，情况 1 和情况 2 也需要大于 1" 的常数。

对于情况 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，这证明了我们最后一项的价值。所以总共有 logc(log(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))).

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

TIme complexity of various nested for loops

big-o

loops

for-loop

time-complexity

asymptotic-complexity