[讨论］如何写出只要用小过三次的LOOP就能找到最大值和最小值

小劲鸭

在书上找了一个问题，想了半天还是不得其解， 看看大家怎么想：

有个整数array, A[],有n个整数值。 现在想一个algorithm 用来找出这个array里的最大值和最小值， 但要求这个algorithm的最大comparisons的数必须小于3n/2, 换句话说， 如果你是用for (int i = 0; i < n; i++)就不行， 因为你最多用了n次比较， 如果是三个loop的话， 就是3n了， 这就违反了这个条件， 我看看书上给的提示是将这个array分成两个， 从A[0 -> 2/n - 1]是Amin[]; 而从A[2/n -> n - 1] 是Amax[]; 这样用loop解决就是n/2了， 但这给出个最大值， 即是只能用2次或者1次loop就要将这两个ARRAY里的最大值和最小值找到， 最后在互相对比， 选出A［］里面的最大值和最小值， 不知道有没有人有些方案呢？

hantsy

it needs use "loop"...

int A[]=new int[100];
Arrays.sort(A);

A[0] is the min
A[99] is the max

小劲鸭

传统的方法我知道， 但怎么才能用少于三个LOOP来完成这个才是问题的关键。。

luma

最初由 小劲鸭 发表
传统的方法我知道， 但怎么才能用少于三个LOOP来完成这个才是问题的关键。。

n个数，每两个数一组，比较n/2次，比较结果的胜者再每两个一组比较n/4次，比较结果的负者也继续每两个一组比较n/4次，然后是n/8次....，总比较次数

n/2 + n/4 * 2 + n/8 * 2 + n/16 * 2 + ....  
=
n + n/4 + n/8 + 16/n + ....
结果收敛于 3n/2

aries1998

看来要好好学习数学啊!

小劲鸭

最初由 luma 发表
n个数，每两个数一组，比较n/2次，比较结果的胜者再每两个一组比较n/4次，比较结果的负者也继续每两个一组比较n/4次，然后是n/8次....，总比较次数

n/2 + n/4 * 2 + n/8 * 2 + n/16 * 2 + ....  
=
n + n/4 + n/8 + 16/n + ....
结果收敛于 3n/2

哇， 这个强，这都给你想到， 厉害。。。:p

hantsy

分组排序，。。。
交换，冒泡，二叉树，。。。
这样啊，，，这种算法可以写一本书了。。。
<数据结构和算法>现在有用java语言描述的。。。

小劲鸭

最初由 hantsy 发表
分组排序，。。。
交换，冒泡，二叉树，。。。
这样啊，，，这种算法可以写一本书了。。。
<数据结构和算法>现在有用java语言描述的。。。

理论上insertion and bubble sort 的最大比较是 O(n^2)， 而binary tree 即是heap sort的最大比较是 O(nlogn)

他们都没办法实现小于3n/2的，只有luma兄的办法好像可以说

lucifer

呵呵，这个只是找到最大最小值，不需要排序的，自然时间复杂度可以小于nlog(n)

zonzi

avl树呢？其实也不用平衡树，只要不平衡的"avl"就够了
最大值=最右边的叶子
最小值=最左边的叶子
谁能告诉我怎么用java来做树呢？