baoleilei6 2020-04-23 19:22:18 
1629 
收藏 9
最近发现了个好东西，就是一个学算法的好东西，是网易公开课的一个视频。
这是麻省理工学院的公开课，有中英字幕，感谢网易。。
也可以在 App 把视频缓存下来之后再放到电脑上面看，因为我这样可以倍速，毕竟每集几乎一个多小时。
回到标题，就是突然顿悟了一样，就知道时间复杂度大概是怎么算的了。
因为在学校上课的时候没听明白，太官方了，而且课下也没钻研时间复杂度这个事，所以一直云里雾里的。
时间复杂度是指渐进式的，是看输入规模的。
我也明白一些基本的，比如什么常数阶，什么去掉低阶项，保留最高项，所以平时也勉勉强强的概括出来。
不多说了，直接看看二分查找的。
我们都知道二分查找在最坏的情况下依次是n/2,n/4,n/8。。。。 一直到1为止，这就有点惨了。
然后，意思就是要循环多少次才能查找到目标数呢，我们假设是 x 次。
然后我们可以观察到分母是每次都乘以 1/2，分子不变，所以可以根据题意列出下面等式：
n(1/2)x = 1
也就是
然后运算一下
最后就是
对数函数的底数省略掉，所以也就是
啧啧，这么简单的东西现在才认真看，服了我自己。。
若有收获，就点个赞吧
0 人点赞
