这些嵌套循环的时间复杂性

Question

关于嵌套for循环的时间复杂性，O（n^2），我遇到过几篇帖子。它是否仍然适用于我在下面提到的两种情况？

案例1：Second for循环的增量不是1，而是每次迭代都乘以2

for (i = 0; i <= n; i++)
{
  for(j = 1; j <= n; j = j*2)
  {
   // Some code
  }
}

案例2：第二个循环以n/2开始，每次迭代递增1。

for (i = 0; i <= n; i++)
{
  for(j = n/2; j <= n; j++)
  {
   // Some code
  }
}

在这两种情况下，n都是一个整数。我认为这两种情况下的时间复杂度都是O（n^2）。这就是实际的时间复杂性吗？

Answer 1

顶部是O（n对数（n）），底部是二次的O（n^2）。

两个外循环显然都是线性的，因此问题归结为确定内循环的复杂度，并将其与各自的外循环复杂度相乘。

对于顶部的内部循环，j重复加倍，创建序列1、2、4、8、16。。。这个内部循环的总迭代次数是n的log2，类似于二进制搜索（或者，重复将n除以一半）。

对于底部的内部循环，迭代从n/2运行到n。2的常数因子被忽略，因此这与从0迭代到n相同，或线性。