问题描述
我的教授刚刚告诉我们，任何将输入长度减半的运算都具有O（log（n））复杂度，这是经验法则。为什么不是O（sqrt（n）），它们都不相等吗？
My professor just taught us that any operation that halves the length of the input has an O(log(n)) complexity as a thumb rule. Why is it not O(sqrt(n)), aren't both of them equivalent?
推荐答案
它们不相等： sqrt（N）将比 log （N）增加更多。没有常数 C ，因此您将 sqrt（N）< C.log（N），用于所有大于某个最小值的 N 值。
They are not equivalent: sqrt(N) will increase a lot more than log(N). There is no constant C so that you would have sqrt(N) < C.log(N) for all values of N greater than some minimum value.
一种简单的方法，是 log （N）的值将接近 N 的（二进制）位数，而 sqrt（ N）是一个数字，其本身的位数是 N 的一半。或者，用等式说明这一点：
An easy way to grab this, is that log(N) will be a value close to the number of (binary) digits of N, while sqrt(N) will be a number that has itself half the number of digits that N has. Or, to state that with an equality:
log （N）= 2log （sqrt（N））
log(N) = 2log(sqrt(N))
因此，您需要采用 sqrt（N）的对数（！）使其复杂度降低至与 log （N）。
So you need to take the logarithm(!) of sqrt(N) to bring it down to the same order of complexity as log(N).
例如，对于11位二进制数0b10000000000（= 2 ），平方根为0b100000，但是对数只有10。
For example, for a binary number with 11 digits, 0b10000000000 (=2), the square root is 0b100000, but the logarithm is only 10.
这篇关于复杂度O（log（n））是否等于O（sqrt（n））？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！