关于基于比较的排序

学术版

xixisuper @ 2025-11-19 22:39:36

基于比较的排序的比较次数下界是 n\ln n 的，有没有大手子能证明一下？

给个相关链接也行。

by lailai0916 @ 2025-11-19 22:40:51

\log_2(n!)=\Theta(n\log n)

by Register_int @ 2025-11-19 22:49:46

@xixisuper 大概就是总共 n! 种可能性，比较一次最多去掉一半，因此总比较次数最少要 O(\log n!)=O(n \log n)。

by Register_int @ 2025-11-19 22:50:48

同理可得上界是 O(n!)，但屁用没有就是了（

by xixisuper @ 2025-11-19 22:52:29

@lailai0916

欧感谢，此帖结

by xixisuper @ 2025-11-19 22:53:19

@Register_int

感谢

|