/* */ John Waken's Blog

John Waken's Blog

Beauty is Simplicity

比较排序的最少比较次数

John Waken posted @ Dec 31, 2009 09:03:01 PM in Algorithm with tags sort , 11068 阅读

比较排序研究

今天在BYR论坛算法版看到一个关于比较排序的问题。题目很经典,如下:给你n个互不相同的数,最少用多少次比较可以完全确定各个数的大小关系。也就是问基于比较的排序最少比较次数是多少?

网上大多数人都是用信息论的思想去理解。这种想法是很好的,不过完全可以正宗的离散数学方法来解决这个问题。下面我给出结果以及证明。

a_{n} 表示将n个互不相同的数(其实相同也没关系,这里是为了让读者更容易理解)排序需要的最少比较次数。

设这n个数是   $$b_{1}, b_{2}, ... \quad,b_{i}, ...\quad b_{n}$$

我们经过m次比较操作确定了每个数之间的关系,记这m次操作如下: $$c_{1},c_{2},...\quad ,c_{i},...\quad c_{m}$$

因为比较操作都是独立的,并不互相影响,所以改变它们的次序对结果无任何影响。我们把所有牵涉到$$b_{n}$$的比较操作都往后移,那么前面的与b_{n}无关的比较操作肯定确定了b_{1}, b_{2}, ... , b_{n-1} 的大小关系,也就是前n-1个数已经排好顺序了。现在只要确定b_{n}在这个排列中的位置就可以了,肯定是用二分查找最快。所以我们可以得到下面的第推式(a字母怎么有两种写法,哪位朋友知道怎么解决吗?):

            $$a_{n} =  a_{n-1} + p_{n-1},  n\geq 3$$                   变换一下得到

            $$a_{n+1} =  a_{n} + p_{n} \quad\quad n \geq 2$$

p_{n}表示往一个含有n个元素的有序排列中插入一个新的元素,并且保证排列仍然有序,所需要的最少比较次数。很多人会认为是 $$log_{2}n$$, 这显然是错误的,因为它可能会得出小数。所以我们要用取整函数要进行调整,我试了下,发现上取整函数、下取整函数都不行,所以我们要发明一个新的取整函 数,我称之为 SuperCeil(超级上取整函数),它和ceil(上取整函数)有点儿像,比如 SuperCeil(1.23) = 2,SuperCeil(2.345) = 3,SuperCeil(7.00001) = 8。但是对整数的处理不一样,ceil(3) = 3,而 SuperCeil(3) = 4;SuperCeil(5) = 6。我想大家应该明白了SuperCeil的意义。这样我们就得到了最终的结果:

           a_{n+1} =  a_{n} + SuperCeil(n) \quad\quad n \geq 2

           初始条件是 a_{2} = 1 , 因为两个数显然比较一次就可以了。


OK,问题应该算解决了,但是还不太严密。关于如何求这个第推式的通项,我还没想出来。先放在此博客上如果您有方法求解,或者发现了错误,请在此博客留言或用邮件通知我。

Chitano 说:
Dec 24, 2010 01:45:32 AM

是说 $$ a_{n+1} = a_{n} + SuperCeil(log_{2}n) \quad\quad n \geq 2$$ 吗? 然而$$a_{4}=5, a_{5}=7=a_{4}+log_{2}4$$ 这里似乎不是SuperCeil吧 另外,过程似乎不太严密,为何前面与$$b_{n}$$无关的操作一定确定了前面n-1个数的顺序?这n-1个数中某些顺序完全可以是在后面与$$b_{n}$$有关的操作中确定的。这里需要证明,一定存在i,使得$$b_{i}$$以外的n-1个数的顺序可以通过与$$b_{i}$$无关的操作的结果决定 另外我可以给出一个下界: 由于n个数的全排列是n!种,而每次比较得到的结果只有2种,因此$$a_{n}$$次比较最多得到$$2^a_{n}$$种可能结果,而每种可能结果最多对应一个n个数的顺序

所以最少比较次数不小于 $$ceil(log_{2}n!)$$

但是我暂时没想到方法证明一定存在这样的比较方案。不过前面到n=8的时候都还正确。

cleaning services ab 说:
Sep 15, 2019 04:36:23 PM

You can provide anyone the services as outlined by your needs even as we own high-pressure tools. The personal hygiene of basements area is for about a fatal task. Currently, you don't have to worry with regards to basement cleanup. Our specialized staff gives you the solutions in rapid sequence. Here are generally major making and towers cleaning solutions we decide to offer you 24 / 7.

maid agency dubai 说:
Sep 04, 2021 04:15:32 PM

Properly cleaning house windows and eliminating hard h2o stains or perhaps spots has a special merchandise you won't find everyday within your local components or food store. The goblet restoration products I take advantage of can become ordered on the web at many different supply retailers. In this informative article I can list several reputable places to order tough water blemish removal products and present you several general here is how to eliminate hard h2o spots using a mini diy hard h2o stain removing tutorial.

cleaning services 说:
Sep 04, 2021 04:36:52 PM

Most people feel that their house is less clean like they would love it to turn out to be. If the case at hand, contact your dwelling cleaning business enterprise and let them know your challenge. Also, it is recommended better to employ a business enterprise that treat grievances in place of hiring less expensive independent skilled tradesmen. So it happens to be all at your decision what particular company you could be hiring for the purpose of such objectives.

net worth 说:
Jul 27, 2022 06:12:41 PM

If you are interested in your favorite actors' net worth and detailed information, please take a look at idol net worth database.

cleaning company dub 说:
Aug 17, 2023 04:37:02 PM

So that they can maintain asset values, most people desire youngster should be do your deep cleaning on the office or home fairly often. However, it is far from always your practical goal if you're. In order to undertake such your deep cleaning up, most people have to rent and also buy cleaning up equipment plus products to implement at home or business.

babysitting services 说:
Oct 17, 2023 05:34:25 PM

We're living within an age whenever life is actually running on the top speed. The competition is really tough that individuals work twenty-four x 7 to be able to protect their own position. Of their time is actually spent for making plans as well as presentations, meeting customers and attempting to reach rigid deadlines. Consequently the home chores tend to be either remaining incomplete or simply not carried out.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter