免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 本题一般情景怎么理解?

(NOIP2006)将5个数的序列排序,不论原先的顺序如何,最少都可以通过(  )次比较,完成从小到大的排序。 A. 6      B.7       C. 8     D. 9.
























答案7,一般公式[$log_2(n!)$]+1,
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

我在某一小册上看到这个问题的(但明确指出是不同的)当时看到这个底是2也是觉得神奇

TOP

回复 1# realnumber
网友给我讲过类似这个的一些知识,应该是属于算法里面的时间复杂度问题,归并排序是基于比较基础的最快的排序方法,说的应该就是那个结果吧,不过最后他用了大O表示。
对程序我都不怎么懂,虽然有兴趣,但是学起来难,只是有时问到一些问题,网友会用程序来给我解释一部分,还要给我解释那个程序,虽然他很有耐心,但我还是有太多地方不懂了,就像和他学高等几何一样,勉强学到一点,但他那个什么三线坐标、重心坐标法计算的,我至今都没学会。

TOP

n!是全部排列数,2^n是放左边还是右边的意思。

TOP

應該向上取整 $\lceil log_2 n!\rceil$

n!是全部排列數,每次比較使排列數分開一半

TOP

返回列表 回复 发帖