//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)。
你能解释一下吗？
如果有疑问，只需用一些值替换n的值，然后试运行两个循环。
让我们以n = 100为例。
//loop1
对于(int i=1；i<=n；i*=2(｛｝
步骤(以i,n的形式(为：
- 1100
- 2100
- 4100
- 8100
- 16100
- 32100
- 64100
-
128100
从技术上讲，它在7步骤中解决。
//loop2
对于(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((。
简短回答：
两者都是Log (n)，因为对于输入n，两个循环都将运行Log(n(次。
由于for循环中的i *= 2，第一个循环运行Log(n(次，但由于for循环的上限直接设置为该值，第二个循环运行Log。
详细信息：
Big-O函数告诉函数的增长率。第二个循环——你对此感到困惑——实际上是两个循环中更简单的一个。您可以直接看到，对于任何输入n，函数将始终只花费与Log(n(成比例的时间。
因此，第二个环路的增长率与Log(n(成比例，或者换句话说，等于O(Log(n((。