最近看了Harvard CS50和Stanford的课程,分享一下2个有趣的事实。
你是否想过电脑是如何处理我们的任务的呢?
比如我们想从词典里面查找mission这个单词,词典有1000页,我们该怎样做?
简单,只需要输入单词即可。但是如何做到呢?我们的app程序应该有一些算法来完成这项工作。
让我们复习一下复杂度与计算时间。
2 如何变快一点?一次翻2页,如果发现单词在前面,则返回前一页,复杂度。
3 第三种方法,我们将词典一分为2,然后查找单词,如果没找到,则继续一分为2。这个方法的复杂度是。
现在我们有了这3种算法,我们需要知道哪个算法更快。
最好的方法是计算函数是怎样增长的。数学上面是计算函数的导数,例如,移动一个物体对时间求导就是这个物体的速度:也就是位移随时间的变化幅度。
回到我们的词典,如果有2000页,需要多少步计算结果呢?
1 1000页的词典需要1000次迭代,线性函数,如果是2000页,就需要增加一倍的迭代。
2 第二种方法增加的速度减缓了一点,因为复杂度是。
3 而对数方法只需要增加1步来计算2000页词典。
下图可以更好的理解这3个函数的不同。显然是性能最好的。
有趣的是对数并不总是最优的,比如函数和函数。
第一张图展现了对数函数的增长比二次方要慢很多。
然而,更仔细的看一下,如果输入数据比较小,那么对数函数会比二次方函数要快一点。
因此,如果你是处理比较小的问题,不使用对数函数可能会更好一些。
又学到了一点小知识,有问题可以留言~