O(logn)到底有多快？

O(logn)到底有多快？

最近看了Harvard CS50和Stanford的课程，分享一下2个有趣的事实。

1. 搜索问题的解决方案
2. log函数与问题数量级

搜索问题的解决方案

你是否想过电脑是如何处理我们的任务的呢？

比如我们想从词典里面查找mission这个单词，词典有1000页，我们该怎样做？

简单，只需要输入单词即可。但是如何做到呢？我们的app程序应该有一些算法来完成这项工作。

让我们复习一下复杂度与计算时间。

1. 第一种方案是我们可以一页一页的翻看词典找到单词，这样会花费时间。如下图：

2 如何变快一点？一次翻2页，如果发现单词在前面，则返回前一页，复杂度。

3 第三种方法，我们将词典一分为2，然后查找单词，如果没找到，则继续一分为2。这个方法的复杂度是。

现在我们有了这3种算法，我们需要知道哪个算法更快。

最好的方法是计算函数是怎样增长的。数学上面是计算函数的导数，例如，移动一个物体对时间求导就是这个物体的速度：也就是位移随时间的变化幅度。

回到我们的词典，如果有2000页，需要多少步计算结果呢？

1 1000页的词典需要1000次迭代，线性函数，如果是2000页，就需要增加一倍的迭代。

2 第二种方法增加的速度减缓了一点，因为复杂度是。

3 而对数方法只需要增加1步来计算2000页词典。

下图可以更好的理解这3个函数的不同。显然是性能最好的。

对数函数在不同量级的表现

有趣的是对数并不总是最优的，比如函数和函数。

第一张图展现了对数函数的增长比二次方要慢很多。

然而，更仔细的看一下，如果输入数据比较小，那么对数函数会比二次方函数要快一点。

因此，如果你是处理比较小的问题，不使用对数函数可能会更好一些。

又学到了一点小知识，有问题可以留言~