algorithm - 给定循环的时间复杂度 O(logn) 或 O(n)

Question

//loop1
for (int i = 1; i <= n; i*=2) { }
//loop2
for (int i = 1; i <= logn; i++) { }

我们和 friend 争论循环，我认为第一个是O(logn)，第二个是O(n)。然而，对于后一个，他说它也是 O(logn) 而不是 O(n)。

你能解释一下吗？

Answer 1

如有疑问，只需替换 n 的值即可使用一些值并试运行两个循环。

我们以n = 100为例例如。

//loop1

for (int i = 1; i <= n; i*=2) { }

步骤(以 i,n 的形式)是:

• 1 , 100
• 2 , 100
• 4 , 100
• 8 , 100
• 16 , 100
• 32 , 100
• 64 , 100
• <罢工>128 , 100

从技术上讲，它解决了 7步骤。

//loop2

for (int i = 1; i <= logn; i++) { }

• log₂(100) = 6.64 ~ 7.
• 步骤(以 i,n 的形式)是:
  • 1 , 7
  • 2 , 7
  • 3 , 7
  • 4 , 7
  • 5 , 7
  • 6 , 7
  • 7 , 7
  • 8 , 7

这也在 7 中得到解决脚步。因此，这两种方法具有相同的复杂度，即 O (log(n))。