一组数中找max或min的最快方法是什么？

deadlylight

我只是想说明，n个item的最佳复杂度不一定就是O(n)
在特殊情况下可能有更好的方法

lenovo

原帖由 deadlylight 于 2007-4-9 11:37 发表
我只是想说明，n个item的最佳复杂度不一定就是O(n)
在特殊情况下可能有更好的方法

一般讨论算法，说时间复杂度，
空间复杂度，都是指的普遍情况。
当然分析时，也会分别指出最好情况下，
最坏情况下，平均情况下等会是多少。
因为每个学过数据结构和算法的人都知道，
在特殊情况下，那些指标当然可能为常量。
这样讨论还有什么意思呢。

cjaizss

原帖由 deadlylight 于 2007-4-9 10:53 发表
排序太慢了
不知道有没有比O(n)更快的方法

没有

tyc611

如果只是找最大或者最小，就没啥好讨论的；如果找前N大或者N小倒还可以讨论下下

cjaizss

原帖由 tyc611 于 2007-4-9 12:15 发表
如果只是找最大或者最小，就没啥好讨论的；如果找前N大或者N小倒还可以讨论下下

找第k大的数存在o(n)算法（与k无关，n为数组长度）

[ 本帖最后由 cjaizss 于 2007-4-9 13:10 编辑 ]

zwylinux

原帖由 deadlylight 于 2007-4-9 10:53 发表
排序太慢了
不知道有没有比O(n)更快的方法

这个不需要排序，但是也不可能比O(n)快

1. 
   
2. void maxmin(int a[], int n){
   
3.   int i,max,min;
   
4. 
   
5.   max=a[0];
   
6.   min=a[0];
   
7.   for (i=1;i<n;++i){
   
8.     if (a[i]>max)
   
9.       max = a[i];
   
10.     else if(a[i]<min)
    
11.       min = a[i];
    
12.   }
    
13. }
    

复制代码

最坏的情况是a中的元素递减排序，这时要比较的次数为2(n-1);
最好的情况是a中的元素递增排序，这时要比较的次数为(n-1);

所以平均比较次数为：
    (2(n-1)+(n-1))/2 = 3n/2-3/2<=3n/2
这应该是对无序数组查找最大最小值的最好方法了，该算法的平均比较次数不多于3n/2;

A.com

找大小和找相同不同，在没有完全处理这个数组前，你不能确定已处理的数里是否已出现最大值和最小值。所以4楼的解决办法就是最简单的了。其复杂度恒等于O（n）

[ 本帖最后由 A.com 于 2007-4-9 12:51 编辑 ]

ArXoR

原帖由 zwylinux 于 4/9/07 12:34 发表


这个不需要排序，但是也不可能比O(n)快

1. 
   
2. void maxmin(int a[], int n){
   
3.   int i,max,min;
   
4. 
   
5.   max=a[0];
   
6.   min=a[0];
   
7.   for (i=1;i<n;++i){
   
8.     if (a[i]>max)
   
9.       max = a[i];
   
10.     e ...

复制代码

你这样还得假设输入的分布

实际上是存在最坏情况下比较次数是 3 * (n + 1) / 2 的算法.

把序列两两分组, 比如当前组 a[ i] 和 a[ i + 1],
先比较他们俩的大小, 然后只用小的去更新min, 大的去更新max.
这样就保证对每组只有3次比较,
考虑上n是奇数的情况, 最坏就 3 * (n + 1) / 2 次了

ArXoR

原帖由 A.com 于 4/9/07 12:49 发表
找大小和找相同不同，在没有完全处理这个数组前，你不能确定已处理的数里是否已出现最大值和最小值。所以4楼的解决办法就是最简单的了。其复杂度恒等于O（n）

无语... 怎么O(n)内排序?

zwylinux

原帖由 ArXoR 于 2007-4-9 13:00 发表


你这样还得假设输入的分布

实际上是存在最坏情况下比较次数是 3 * (n + 1) / 2 的算法.

把序列两两分组, 比如当前组 a[ i] 和 a[ i + 1],
先比较他们俩的大小, 然后只用小的去更新min, 大的去更新max. ...

这个算法没有假设输入分布啊