//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)
。
你能解释一下吗?
最佳答案
如有疑问,只需替换 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++) { }
- log2(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))。
关于algorithm - 给定循环的时间复杂度 O(logn) 或 O(n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53190330/