复杂度为O(logn)和O(log(sqrt(n)))之间的区别。

Question

考虑以下内容：

log(sqrt(n)) = (1/2)log(n)

如果我们在渐进分析中不考虑常数项，那么O(log(sqrt(n)))是否和O(log(n))一样好？

在我看来，如果我们增加n的大小，log(sqrt(n))将比log(n)增长缓慢。但我无法理解把(1/2)的幂移到前面的缺陷是什么？难道只有1/2因素减缓了速率吗？

考虑当我们把log(n*n)表示为2log(n)和log(n)的情况。

- codenamefreak47

---

为什么不在Wolframalpha中同时可视化这两个图形呢？ - bobah

@bobah，也许codenamefreak47想知道如何自己解决问题。 - AakashM

Answer 1

在渐进意义下它是相同的:

O(log(sqrt(n))) = O(log(n^1/2)) = O(1/2 log(n)) = O(log(n))

- Eugen Martynov

Answer 2

Time(A) = log n

Time(B) = log sqrt(n) = log n^(1/2) = 1/2 log n

渐进相等

O(Time(A)) = O(log n)

O(Time(B)) = O(1/2 log n) = O(log n)

O(Time(A)) = O(Time(B))

微不足道的差别

Time(A) = 1   * log n

Time(B) = 1/2 * log n

Time(A) > Time(B)

Time(A) = 2 * Time(B)

结论

log n = 2 log sqrt(n)

尽管log n和log sqrt(n)之间的差异微不足道，但log n始终需要双倍于log sqrt(n)所需的时间。

视觉效果：

- Khaled.K

Answer 3

你是对的，根据你问题中的推理，O(log(sqrt(n)))与O(log(n))是相同的。

- Henry

Answer 4

大O符号忽略任何常数倍数。

O(500000.N)是O(N)，也是O(0.00001.N)。

出于同样的原因，O(Log(Sqrt(N)))是O(1/2.Log(N))，也是O(Log(N))，在任何基数下都是如此。

大O符号与程序速度无关，它关注的是随着N的增长，运行时间的增长。

- user1196549