考虑
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) 时的情况?
最佳答案
渐近相同:
O(log(sqrt(n))) = O(log(n^1/2)) = O(1/2 log(n)) = O(log(n))
关于algorithm - 复杂度 logn 和 log(sqrt(n)) 的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23904478/