复杂度O（log（n））是否等于O（sqrt（n））？
我的教授刚刚告诉我们，任何将输入长度减半的运算都具有O（log（n））复杂度，这是经验法则。为什么不是O（sqrt（n）），两个都不相等？
回答：
它们不是等效的： sqrt（N）的 增长将比 log 2（N）_大得多。没有常数 _C， 因此对于所有大于某个最小值的 N 值，您都将拥有
sqrt（N） <C.log（N）。 __
一个简单的方法来抓住这个，是 日志 2（N）_将是一个值接近的（二进制）位的数目 _Ñ ，而 SQRT（N）
将是一个数，其具有自身的位数的一半数量的 Ñ 具有。或者，用等式声明：
log 2（N）= 2log 2（sqrt（N））
因此，您需要使用 sqrt（N） 的对数（！）使其复杂度降低到与 _log 2（N）_相同的顺序。
例如，对于11位二进制数字0b10000000000（= 2 10），平方根为0b100000，但对数仅为10。
以上是 复杂度O（log（n））是否等于O（sqrt（n））？ 的全部内容， 来源链接： utcz.com/qa/402913.html
