【算法随想】排序算法的极限在哪里?


\(n\) 个元素有 \(n!\) 种排列方式,每次比较可以获取 \(1b\) 的信息量,因此获得足够的用于比较的信息量需要的次数是 \({\log _2}(n!) \in \Omega (n\log n)\).

当然了还有一个最低的复杂度下界 \(\Omega (n)\) ,程序总得把输入的数据读完,难道不是么?


文章作者: sfc9982
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
  目录