算法-时间复杂度

发表于 更新于 分类于 阅读次数： 本文字数： 361 阅读时长 ≈ 1 分钟

时间复杂度 O(log n)

摘录至网络文章

O(1) 表示一次操作即可直接取得目标元素（比如字典或哈希表）
O(n) 意味着先要检查 n 个元素来搜索目标
O(log n) ？？

最好情况下二分搜索的时间复杂度是 O(1)，最坏情况（平均情况）下 O(log n)
我们直接来看最坏情况下的例子。已知有 16 个元素的有序数组。
举个最坏情况的例子，比如我们要找的是数字 13。

5188365c.png

选中间的元素作为中心点（长度的一半）
e5638205.png
db17e76b.png

13 小于中心点，所以不用考虑数组的后一半

c19fa0b1.png

重复这个过程，每次都寻找子数组的中间元素

35805851.png ae29491c.png

每次和中间元素比较都会使搜索范围减半。
所以为了从 16 个元素中找到目标元素，我们需要把数组平均分割 4 次，也就是说，

3db34241.png

简化后的公式类似的，如果有 n 个元素，

c4bdeccd.png

归纳一下

fabc58cf.png

分子和分母代入指数

0bc090ed.png

等式两边同时乘以 2^k

fbbdb8b9.png

最终结果可以写成对数形式：得数就是最多找几次

892636ac.png

所以 log n 的确是有意义的。