最坏复杂度

一句话理解

最坏复杂度看最倒霉的那组数据。

为什么要学

评测可以专门卡你最坏情况。

讲解

快速排序平均 n log n，最坏 n²。竞赛用的 sort 做了防护，但你自己写的算法要按最坏分析。

“平均很快”不能当证明。

例子

链表在哈希表最坏时可能退化成一条链。

常见错误

• 只测随机数据。
• 把期望当成最坏。