吃下这颗栗子，秒懂常见时间复杂度

二分查找的时间复杂度为什么是O(logn)？...





封面图：雨儿胡同，这个夏天适合逛胡同

如果你还不太懂算法的“大O分析法”，建议你先看下《学会大O分析法再去面试吧》。

举个栗子

作为老师的你，正站在教室里所有学生（假设有n名学生）前面。他们中有一个调皮学生拿了你的笔。现在你要找到那个调皮孩子。你有几种方法？每种方法的时间复杂度是多少？

O(1) 常数阶

询问之前，检查下自己的包。法克！笔在自己包里。 此时，询问次数与学生数量(问题规模)没有关系。

O(n) 线性阶

询问每个学生“是你拿了我的笔吗？”，如果不是，继续询问下一个。最坏的情况，你要询问n次。

O(n²) 平方阶

询问一个学生，“是林蛋大拿了我的笔吗？不是？那是楚中天拿了我的笔吗？”就这样，向他询问其他每个学生。如果在第一个学生那没有得到答案，继续询问下一个学生。向每个学生询问其他所有学生。最坏的情况你要询问n² 次。

O(log n) 对数阶

把学生分成左右两队，然后询问：“拿我笔的同学在左边吗？不是？那就是在右边喽”。把右队再分成两小队，继续问：“在左边吗？”。最坏的情况你要询问log n次。

O(n log(n))

每个学生都声称自己知道谁拿了笔（实际上只有一个学生知道）。每个学生都要玩一次分半查找的游戏（log(n)）。最坏的情况要找n*log(n)次。



二分查找为什么是O(log n)

如果想通过程序询问“在左边还是在右边？”，就要先把样本集合处理一下。把集合中的所有元素构建成一棵有序的二叉树，然后从根节点开始询问（if判断）。对于一颗完全二叉树( complete binary tree)，我们每判断一次，节点数(查找空间)就会减少一半。最坏的情况我们要判断到二叉树的最深层，也就是查找空间等于1的时候。

所以，n = 2^x   n是节点数，x是查找次数

所以，x = log2(n)   以2为底，n的对数

“大O表示法”不关心常量因子，底数是2还是10只是常量级的差别。所以二分查找的时间复杂度是O(log n)。



一棵茁壮的完全二叉树


公众号：更喜欢编程

长按 关注

解锁更多高难度姿势

    关注 更喜欢编程