和地点一样分析

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/7739917.html

  作者:窗户

  QQ:6679072

  E-mail:6679072@qq.com

  这一篇是上一篇《12(13)个球1个不等重量称3次称出的详细深入分析》的姊妹篇,剖析花招同出一辙,此题源于《算法导论》。

  和地点同样剖判,5个数的排列总共有5!=120种,排序的本质是从那120种排列中规定里头的一种;而每一遍相比较会有三种结果,小于、大于等于。7次比较总共有27=128种结果,用最多128种相比结实去分辨120种排列,是有希望的。解答进度中浸泡着大量的排列组合总括以总计出各个采纳所要分辨的恐怕性数量,总结起来只怕并不自在。时刻要记住一点,不断用消息论下界来清除可能,但音信论下界只好用来破除,而一点办法也想不出来到位一定。

  图片 1

图片 2

  用圈和叉代表数,三个数里面假使存在连线,代表线下边包车型客车数超越等于线上面包车型大巴数。

  每一步多个叉代表本步选取来比较的三个数。

  当5个数用一条线串在共同,当然就是排序甘休。

  同一行也许有两种处境,作者都标了出来。

相关文章