⚠️ NP-hard 意味着什么
某个问题被证明是 NP-hard。这告诉你【0】。
阅读更多 →
近似算法给的是什么样的保证
一个 2-近似算法，保证的是【0】。
阅读更多 →
🔴 固定策略随输入变，随机策略的期望不变
三个输入：已排好序、完全逆序、乱序。固定取第一个当 pivot 各比多少次？再判一下随机 pivot 的期望在这三个输入上是不是同一个数。
阅读更多 →
🔴 期望正好等于那个平均
随机快排的期望比较次数，和"固定取第一个"在全部 120 种输入上的平均，把这两个数比一比。用分数算，别用浮点。
阅读更多 →
🔴 最坏输入里，就有已经排好序的那个
算出最坏比较次数之后，再看看已经排好序的那个输入(0,1,2,3,4) 花了多少次，以及它是不是正好就在最坏那一档。
阅读更多 →
自己写：数出快排的比较次数
补全划分那两步，输出 120 种输入里的最坏比较次数和总和。
阅读更多 →
120 种输入的比较次数加起来是多少
把全部 120 种排列的比较次数加总： from itertools import permutations def qs_cmp(a): """总是拿第一个当
阅读更多 →
固定取第一个，最坏和最好各多少次
五个元素的全部 120 种排列，快排总是拿第一个当 pivot，比较次数的最大值和最小值： from itertools import permutations def qs_cmp(a):
阅读更多 →
⚠️ 「期望」和「平均情况」差在哪
随机快排的期望复杂度，和普通快排的平均情况复杂度，区别是【0】。
阅读更多 →
随机化解决的是什么麻烦
快排里把"取第一个"换成"随机取一个"，解决的是【0】。
阅读更多 →