Dav*_*vid 2 algorithm comparison
从4个不同元素中找到最大元素所需的最小比较次数是多少？我知道5个不同的数字是6,floor(5/2)*3; 这是来自clrs书.但是我知道找到这个没有一个通用公式,或者在那里？
编辑澄清
这4个元素可以是任何不同的顺序(对于这4个元素的所有排列)我对计数技术不感兴趣,以便在遍历元素时跟踪最大元素,但比较如>或<.
最少4个元素.比较次数为3次.
通常,要找到最大的N元素,您需要N-1进行比较.这为您提供4个5个数字,而不是6个.
证明:
总有一个N-1比较解决方案:只比较前两个然后选择较大的并与下一个进行比较,选择较大的并与下一个比较等....
没有更短的解决方案,因为这个解决方案不会比较所有元素.
QED.