algorithm - 复杂度 logn 和 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) 时的情况？

Answer 1

渐近相同:

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