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

Question

我看过几篇关于嵌套 for 循环的时间复杂度为 O(n^2) 的帖子。我在下面提到的两种情况是否仍然适用？

情况 1：第二个 for 循环的增量不是 1，而是每次迭代都乘以 2

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

情况 2：第二个 for 循环以 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 log(n))，下面的是二次方，O(n^2)。

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

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

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

Time Complexity of these nested loops