| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 8317 人关注过本帖
标题:[代码贴]在一个数组中寻找最大值和最小值所需要进行比较的次数
取消只看楼主 加入收藏
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
以下是引用lmlm1001在2017-7-13 23:43:45的发言:

to 14楼:
 
数组 n = 4, array = 1, 2, 3, 4  
3次具体步骤:
取 1,双赋值。
和2比对,先判断最大值,2 > 1,跳过最小值
和3比对,先判断最大值,3 > 2,跳过最小值
和4比对,先判断最大值,4 > 3,跳过最小值
 
6次具体步骤:
取 1,双赋值。
和2比对,先判断最小值,再判断最大值
和3比对,先判断最小值,再判断最大值
和4比对,先判断最小值,再判断最大值
 
数组 n = 5 略


你执行程序后就会看到具体的比较过程,比你这么猜测的强的多
2017-07-13 23:54
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
另外,看我在1楼最上面写的哪一段话的最后一句解释。
2017-07-13 23:55
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
以下是引用lmlm1001在2017-7-13 23:43:45的发言:

to 14楼:
 
数组 n = 4, array = 1, 2, 3, 4  
3次具体步骤:
取 1,双赋值。
和2比对,先判断最大值,2 > 1,跳过最小值
和3比对,先判断最大值,3 > 2,跳过最小值
和4比对,先判断最大值,4 > 3,跳过最小值
 
6次具体步骤:
取 1,双赋值。
和2比对,先判断最小值,再判断最大值
和3比对,先判断最小值,再判断最大值
和4比对,先判断最小值,再判断最大值
 
数组 n = 5 略

代码中所用的算法,压根就不是你这么想的。
2017-07-13 23:58
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
以下是引用lmlm1001在2017-7-14 00:14:38的发言:

 
我是说你这句话有问题,至少在我提出的情况下是不对的。
如果你的程序是为了验证这句话的正确性的话,那么就没有必要;
如果你的这句话是总结你的程序的话,那么我提出的情况就是没有必要的。
 
附 “我这么猜测” 的代码。
 
for( max = array[0], min = array[0]; i < arraysize; ++i )
    if( array > max )
        max = array;
    else if( array < min )
        min = array;
    else
        NULL;
 
for( max = array[0], min = array[0]; i < arraysize; ++i )
    if( array < min )
        min = array;
    else if( array > max )
        max = array;
    else
        NULL;

嗯,你猜的的代码所用的是算法A,我贴出来的代码所用的是算法B。算法A和算法B是不同的,所以需要比较的次数也是不同的。你用的算法的比较次数大概是2*(n-1)。在海量数据下,理论上算法B所用的时间比算法A少了25%。实际,上两数比较所消耗的性能是非常客观的,所以在程序设计时尽量减少两数的比较次数,可以显著地提升性能。


[此贴子已经被作者于2017-7-14 00:46编辑过]

2017-07-14 00:38
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
我贴出这个代码,实际上是因为最近的一个项目中类似的导致了一个性能问题,引导大家在这方面思考一下。并非想得到一个什么结论或是细究某些细节。
2017-07-14 00:48
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
以下是引用lmlm1001在2017-7-14 01:03:16的发言:

按照你的算法
当 n = 2 时,比对次数是1
实际是2, min一次 max一次
times是1

我在之前的某层楼说过,不要探究一些不必要的细节。当你知道两个数谁是较小的之后,还会在比较一次来判断谁是较大的数吗?
2017-07-14 08:03
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
以下是引用lmlm1001在2017-7-14 01:11:06的发言:

另外 我认为你for循环中一个循环是固定的6次比对
而且参数似乎有问题

不知道你说的这个for循环到底指的是哪一个?还是那句话,不是主要问题,没必要探究细节。
2017-07-14 08:08
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
#define GetMinAndMax(a, b, minimum, maximum, times) \
({ \
    unsigned int arg1 = (a); \
    unsigned int arg2 = (b); \
    unsigned int temp; \

    (minimum) = arg1; \
    (maximum) = arg2; \
    if((minimum) > (maximum)) \
    { \
        temp = (minimum); \
        (minimum) = (maximum); \
        (maximum) = temp; \
    } \
    (times)++; \
    printf("time %3d: Compared %3d and %3d\n", times, arg1, arg2); \
})

[此贴子已经被作者于2017-7-14 08:19编辑过]

2017-07-14 08:11
八画小子
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:37
帖 子:709
专家分:2063
注 册:2010-11-11
收藏
得分:0 
我知道,26楼的代码(没校验正确性)才能让你觉得算法看起来像是比较了1次而非两次。但两种代码在算法上其实是等效的。算法是一种逻辑上的实现,而代码是物理上的实现。两者本质是一样的,但你不能说算法实现和物理实现就不一样。
这就如同有个人问你吃饭吗?你可以回答“吃。”,你也可以回答“嗯,正好我有些饿了,我顺便吃了吧。”你不能说这两种回答是不同的意思吧?
当讲求算法是,是不需要(或者说不应该)讲求细节的,因为算法是代码的本质,代码是算法的体现,两者是互相统一的。
2017-07-14 08:17
快速回复:[代码贴]在一个数组中寻找最大值和最小值所需要进行比较的次数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.014948 second(s), 9 queries.
Copyright©2004-2025, BC-CN.NET, All Rights Reserved