\(n\) 个元素有 \(n!\) 种排列方式,每次比较可以获取 \(1b\) 的信息量,因此获得足够的用于比较的信息量需要的次数是 \({\log _2}(n!) \in \Omega (n\log n)\).
当然了还有一个最低的复杂度下界 \(\Omega (n)\) ,程序总得把输入的数据读完,难道不是么?
\(n\) 个元素有 \(n!\) 种排列方式,每次比较可以获取 \(1b\) 的信息量,因此获得足够的用于比较的信息量需要的次数是 \({\log _2}(n!) \in \Omega (n\log n)\).
当然了还有一个最低的复杂度下界 \(\Omega (n)\) ,程序总得把输入的数据读完,难道不是么?