给定循环的时间复杂度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).

你能解释一下吗？

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逐步解决.

//循环2

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)).