程序员必懂的四种查找效率：O(1)、O(log n)、O(n)、O(k)

同样是查东西为什么有人1秒有人要1小时今天想和大家聊一个所有程序员都绕不开但初学者往往一脸懵的概念——时间复杂度。别被这个名词吓到其实它就在我们身边。看完今天这篇文章你不仅能搞懂这些“天书”是什么意思还能在下次和同事聊天时淡定地来一句“你这个算法是 O(n) 的太慢了我帮你优化到 O(log n) 吧。”一、先搞懂O() 到底是什么想象你要在一个书架上找一本书。我们找书的具体方法比如一本本找或者先分类再找其实就是算法。而 O()就是用来评价这个算法效率高低的评分标准。这个评分标准看的不是“具体耗时几秒”而是随着书的数量变多你找书的时间会怎么变化。如果书架上只有10本书什么方法都快。但如果有10万本书有的方法还是很快有的方法就会慢到让你怀疑人生。O() 就是用来描述这种“抗压能力”的数学符号。下面我们用找东西的场景把这四种效率挨个讲明白。二、O(1) —— 效率之王“瞬间移动”O(1) 的意思是不管数据有多少我都能一步到位。生活场景假设公司有1000个工位每个工位上都贴着员工的名字。你想找张三。最高效的方法是什么公司发了一张工位地图地图上直接标着“张三 → 工位号 3-205”。你看一眼地图一步到位直接走到那个工位。计算机场景哈希查找在代码里有一种数据结构叫哈希表比如 JavaScript 里的对象、C# 里的字典。# 假设我们存了员工信息staff {张三: 工位 3-205,李四: 工位 2-101,# ... 还有998个人}# 找张三position staff[张三] # 瞬间拿到结果不管staff有多大这就是O(1)数据量从1000变成100万查找时间完全不变永远是瞬间。三、O(log n) —— 效率亚军“每次排除一半”O(log n) 的意思是每次操作都排除一半数据翻倍我也不怕。生活场景朋友说“我心里想了一个1到100之间的数字你来猜我告诉你‘大了’还是‘小了’。”普通人的笨办法是从1开始猜1小了。2小了。3小了……这是 O(n)。聪明人的办法是50大了。25小了。37小了。43大了。40对了每次猜完剩下的范围就减少一半。100个数最多猜7次1000个数最多猜10次100万个数最多猜20次。这就是 O(log n)。计算机场景二分查找在有序数组里找一个数用的就是这种方法。# 在有序数组里找66arr [2, 5, 8, 12, 19, 23, 34, 45, 56, 66, 78, 89]# 二分查找的过程# 1. 看中间的数 3466比34大只查右半边# 2. 看右半边的中间 66正好命中为什么叫 log nlog n 在数学里叫“对数”你可以简单理解为2的多少次方等于 n。2⁶ 64所以 log₂64 62⁷ 128所以 log₂128 7n 从64涨到128翻了一倍但查找次数只从6涨到7只加了1次。这就是 O(log n) 的可怕之处——数据越多优势越大。四、O(n) —— 老实人“一个一个来”O(n) 的意思是最坏情况下每个东西我都要看一遍。生活场景早上出门钥匙找不到了。你从床头柜开始翻翻书桌翻沙发翻厨房……一个地方一个地方地找。如果房间里有 n 个地方可能藏钥匙最坏的情况下你要把 n 个地方都翻一遍。这就是 O(n)。计算机场景顺序查找在无序数组里找一个数只能用这个方法。# 在乱序数组里找66arr [34, 78, 12, 56, 89, 2, 23, 66, 45, 5, 19, 8]for num in arr:if num 66:print(找到了)break运气好可能第一个就是运气不好可能最后一个才是最坏情况就是n 次。数据对比数据量O(log n) 次数O(n) 次数10071001万141万100万20100万当数据量到100万时O(log n) 只要20次O(n) 要100万次。5万倍的差距五、O(k) —— 我只找该找的O(k) 的意思是这事儿需要干多少活取决于“有多少个目标”而不是“总共有多少东西”。生活场景全班50个人你要收没交作业的那几个人。老师告诉你“就那5个没交”你直接去找那5个人。不管全班是50人还是500人只要没交作业的还是那5个你的工作量就不变。这里的 k 5没交作业的人数n 50全班人数但如果k值很大那么也会影响效率。六、从“查东西”看透算法效率快慢排名一般情况下O(1) O(log n) O(k) O(n)但注意O(k) 的位置不固定——如果 k 很小比如 k10它可能比 O(log n) 还快如果 k 很大比如 kn/2它可能接近 O(n)所以 O(k) 的“快慢”完全取决于k 本身有多大因此它的效率受K值大小而影响。七、看完这篇文章闭上眼睛回想一下O(1)是什么—— 看地图找工位一步到位O(log n)是什么—— 猜数字每次排除一半O(n)是什么—— 找钥匙每个地方翻一遍O(k)是什么—— 收作业只找没交的那几个八、下次写代码时记得问自己三个问题我到底要处理多少数据n 有多大我是不是真的需要处理全部能不能只处理 k 个有没有办法每次排除一半能不能变成 O(log n)想清楚这三件事你就已经超过一半的程序员了。