各种嵌套for循环的TIME复杂度

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（logn）。

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（logn）是怎样的？

Answer 1

如果循环1和循环2中的c=1，那么它将无限次地运行，但它被给出对数时间为什么？

是的，你是对的，如果c=1，那么我们将得到情况1和情况2的无限循环，因此条件“c是大于1的[n整数]常数”对于情况1和情况2也是必要的，以便得到O（logn）复杂度。

对于情况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（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））。