复杂度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))

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)

视觉的

Answer 3

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