请教2^N个数，要找到最大的元素，最少的比较次数要多少？

ztkx

当然不是，比如 a>b,c>d,那么只需要比较 a,c就可以了。
这应该是所谓的natural merge。
asdmonster 发表于 2010-09-14 09:01

a>b是谁告诉你的呢，你又怎么告诉机器的呢?

就算是已排好序的a,b,c,d,e，也仍然需要n-1次比较，

               1
          1        1
     1        1        1

不管是 merge， heap，还是fast，最优的计算复杂度是log_2 N是不错，但是比较次数，Sigma i = 0..(log_2 N)-1  2^i（不知道怎么写公式，还算写清楚了吧）

btw, 2^N是个幌子，其实和指数没有什么关系，看成N就好了

asdmonster

难道我看错了？什么叫“最大的元素”？

狗气球

2^N - 1

starwing83

是说“比较次数”？

允许位操作么？

1和0的比较是不是也叫“比较操作”呢？

linfenghuaster

回复 14# starwing83


    是的，题目就说有那么多数，然后找出最大的，需要最少的比较次数

starwing83

好吧，找最大，恐怕只能2^N-1了= =

ypmei