UOJ Logo Alextokc的博客

博客

一道难题

2017-10-22 12:22:38 By Alextokc

相关链接:http://oeis.org/A036604

题目大概的意思是问你任意n个数,将这n个数排好序的最少比较次数,比如n = 5的时候,次数就为7。

(可以比较数列中的任意两个数,而不是必须相邻的两个才可交换)

评论

WrongAnswer
题意应该是求对n个数排序的最坏情况下最优的比较排序算法,在最坏情况下的比较次数。 我用暴搜跑出了n=1,2,...,7,都是对的。
kczno1
这个东西好像在初赛卷子里见过啊,听说答案就是log2(n!)
worse
好像在TAOCP的第三卷里见过,感觉挺难的。。
liu_cheng_ao
比较排序的效率上界问题?算导里面给了一堆reference……貌似现在没什么效率太高的解法

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。