在整数数组中查找max / min的最快算法是什么？ [英] What the fastest algorithm for find max/min in an array of integers?

问题描述

我知道，只有一个简单的：


#include< stdio.h>


int main（）

{

int min = 0，max = 0，i，arr [12];

for（i = 0 ; i< 12; i ++）

arr [i] = rand（）％31-10;

for（i = 0; i< 12; i ++）

printf（"％d \ t"，arr [i]）;

printf（" \ n"）;

for （i = 0; i< 12; i ++）

{

if（arr [max]< arr [i]）

max = i;

}

for（i = 0; i< 12; i ++）

{

if （arr [min]> arr [i]）

min = i;

}

printf（" \ nmax是： ％d \ n"，arr [max]）;

printf（" \ nmin is：％d \ n"，arr [min]）;

返回0;

}

解决方案

在文章< fu ******* ***@news4.netvision.net.il>，

Eugeny Myunster< bo*@eugeny.wswrote：

>我知道，只有一个简单的：


你不会更快地得到它。除非您以特殊方式存储

数据（例如排序），否则您将需要

查看所有元素。


一些可能提高速度的小改动：


- 你可以在1而不是零开始循环。没有必要比较

arr [0]对自己;

- 将最小值和最大值存储在变量中，而不是将数据引用作为
每次检索它们;

- 在数组的一个循环中计算两者;

- 如果它低于最小值，它就不会更多比最大值。


你真的需要让它更快吗？描述你的整个计划

，看看这是否重要。


- Richard

-

：wq

文章< fu ********** @ news4.netvision.net.il>，

Eugeny Myunster< bo*@eugeny.wswrote：

我知道，只有简单的一个：


#include < stdio.h>


int main（）

{

int min = 0，max = 0，i， arr [12];

for（i = 0; i< 12; i ++）

arr [i] = rand（）％31-10;

for（i = 0; i< 12; i ++）

printf（"％d \ t"，arr [i]）;

printf （" \ n"）;

for（i = 0; i< 12; i ++）

{

if（arr [ max]< arr [i]）

max = i;

}

for（i = 0; i< 12; i ++）

{

if（arr [min]> arr [i]）

min = i;

}

printf（" \ nmax是：％d \ n"，arr [max]）;

printf（" \ nmin是：％d \ n"，arr [min]）;


返回0;

}

Quicksort数组，然后获取第一个（最小）和最后（最大）值？


-

Don Bruder - da **** @ sonic.net - 如果你的来自：地址不在我的白名单上，

或邮件的主题不包含确切的文字PopperAndShadow

某处，发送给此的任何邮件地址将进入垃圾，没有我的

，知道它到了。对不起...< http://www.sonic.net/~dakiddfor more info

Don Bruder< da **** @ sonic.netwrites：

文章< fu ********** @ news4.netvision.net.il>，

Eugeny Myunster < bo*@eugeny.wswrote：

>我知道，只有一个简单的：

[snip]

>

Quicksort数组，然后获取第一个（最小值）和最后一个（最大值）值？

嗯，没有。对数组进行排序通常是O（N * log N），而找到

线性搜索中的最小值和最大值是O（N）。


（旁注：我猜你的意思是qsort。请记住

标准库例程qsort并不一定使用quicksort

算法。）


-

Keith Thompson（The_Other_Keith）< ks *** @ mib.org>

诺基亚

我们必须做点什么。这是事情。因此，我们必须这样做。

- Antony Jay和Jonathan Lynn，是部长

I know, only simple one:

#include <stdio.h>

int main()
{
int min=0,max=0,i,arr[12];
for(i=0;i<12;i++)
arr[i]=rand()%31-10;
for(i=0;i<12;i++)
printf("%d\t",arr[i]);
printf("\n");
for(i=0;i<12;i++)
{
if(arr[max]<arr[i])
max=i;
}
for(i=0;i<12;i++)
{
if(arr[min]>arr[i])
min=i;
}
printf("\nmax is: %d\n",arr[max]);
printf("\nmin is: %d\n",arr[min]);

return 0;
}

解决方案

In article <fu**********@news4.netvision.net.il>,
Eugeny Myunster <bo*@eugeny.wswrote:

>I know, only simple one:

You''re not going to get it enormously faster. Unless you store the
data in a special way (sorted for example), you''re going to have to
look at all the elements.

Some small changes that might improve speed:

- you can start the loop at 1 rather than zero. No point comparing
arr[0] against itself;
- store the min and max values in variables, rather than doing
an array reference to retrieve them each time;
- calculate both in one loop through the array;
- if it''s less than the minimum, it won''t be more than the maximum.

Do you really need to make it faster? Profile your whole program
to see if this is important.

-- Richard
--
:wq

In article <fu**********@news4.netvision.net.il>,
Eugeny Myunster <bo*@eugeny.wswrote:

I know, only simple one:

#include <stdio.h>

int main()
{
int min=0,max=0,i,arr[12];
for(i=0;i<12;i++)
arr[i]=rand()%31-10;
for(i=0;i<12;i++)
printf("%d\t",arr[i]);
printf("\n");
for(i=0;i<12;i++)
{
if(arr[max]<arr[i])
max=i;
}
for(i=0;i<12;i++)
{
if(arr[min]>arr[i])
min=i;
}
printf("\nmax is: %d\n",arr[max]);
printf("\nmin is: %d\n",arr[min]);

return 0;
}

Quicksort the array, then grab the first (min) and last (max) values?

--
Don Bruder - da****@sonic.net - If your "From:" address isn''t on my whitelist,
or the subject of the message doesn''t contain the exact text "PopperAndShadow"
somewhere, any message sent to this address will go in the garbage without my
ever knowing it arrived. Sorry... <http://www.sonic.net/~dakiddfor more info

Don Bruder <da****@sonic.netwrites:

In article <fu**********@news4.netvision.net.il>,
Eugeny Myunster <bo*@eugeny.wswrote:

>I know, only simple one:

[snip]

>
Quicksort the array, then grab the first (min) and last (max) values?

Um, no. Sorting the array is typically O(N*log N), whereas finding
the min and max in a linear search is O(N).

(A side note: I''m guessing that you mean qsort. Remember that the
standard library routine qsort doesn''t necessarily use the quicksort
algorithm.)

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

这篇关于在整数数组中查找max / min的最快算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！