O(log(N))是什么意思

这里借用那个著名故事《国王赏麦》来直观的解释O(log(N))。

传说西塔发明了国际象棋而使国王十分高兴，他决定要重赏西塔。西塔说：“我不要你的重赏，陛下，只要你在我的棋盘上赏一些麦子就行了。在棋盘的第1个格子里放1粒，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，依此类推，以 后每一个格子里放的麦粒数都是前一个格子里放的麦粒数的2倍，直到放满第64个格子就行了”。区区小数，几粒麦子，这有何难，“来人”，国王令人如数付给西塔。计数麦粒的工作开始了，第一格内放1粒，第二格内放2粒，第三格内放4粒。还没有到第二十格，一袋麦子已经空了。一袋又一袋的麦子被扛到国王面前来。但是，麦粒数一格接一格飞快增长着，国王很快就看出，即便拿出全国的粮食，也兑现不了他对西塔的诺言。

从西塔的角度看，每多一个格子他就可以多获得一倍的麦粒，这是个幂运算。而对数计算是幂运算的逆运算，想要直观的理解它，我们可以从西塔对面的视角，也就是国王的角度来看这次赏麦是一个什么样的游戏——我每多提供一倍的麦子，他只多消耗一个格子。而这其实就是O(log(N))的本质：输入规模翻倍，操作次数只增加一。所以这真的是一个非常非常低的时间复杂度。比起O(N)它更接近O(1).

如何达到O(log(N))

如果要设计一个算法，让其具有O(log(N))的时间复杂度，从正面思考是困难的。我们不妨想一想有没有什么操作是每操作一次，需要处理的规模就小一半的。对，特别经典的例子就是二分搜索。每次取中位数，在其左或其右继续搜索目标值。其本质就是每搜索一次，就把待搜索的数据量减小了一半。在这之上还有二分搜索树，O(log(N))其实就是二分搜索树的高度。

总结：

1. 时间复杂度指的是随着输入大小的增长，运行时间会以怎样的速度扩张。
2. O(log(N))指的是 该算法随着输入规模翻倍，操作次数只增加一。