algorithm - 复杂度 O(log(n)) 是否等同于 O(sqrt(n))？

Question

我的教授刚刚告诉我们，根据经验法则，任何将输入长度减半的操作都具有 O(log(n)) 复杂度。为什么不是O(sqrt(n))，两者不是等价的吗？

Answer 1

它们不等价:sqrt(N) 将比 log₂(N) 增长得更快。没有常量 C，因此 sqrt(N) < C.log(N) 对于 N 的所有值都大于某些值最小值。

理解这一点的一个简单方法是，log₂(N) 将是一个接近于 N< 的(二进制)位数的值/em>，而 sqrt(N) 将是一个数字，其本身的位数是 N 的一半。或者，以相等的方式声明:

log₂(N) = 2log₂(sqrt(N))

因此，您需要取 sqrt(N) 的对数 (!) 以将其降低到与 log₂(N )。

例如11位二进制数0b10000000000(=2¹⁰)，其平方根为0b100000，但对数仅为10。