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

Question

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

我们和我的朋友争论我认为第一个是循环，O(logn)而后者是循环O(n)。但是，对于后者，他说O(logn)也不是O(n)。

你能解释一下吗？

标签： algorithmtime-complexitybig-ocomplexity-theory

Answer 1

每当有疑问时，只需n用一些值替换值并空运行两个循环。

让我们举个n = 100例子。

//循环1

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步解决。

//循环2

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

• 日志₂ (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))。