在阵列找最大值和最小值

记录学习内容。
以下内容和截图大多引用文章。
还不了解,内容可能有错误。

在一个阵列,找最大值和最小值,减少比较次数。

Maximum and minimum of an array using minimum number of comparisons
https://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

第一种方式,就是一般的想法 。

写一个回圈 ,跑一遍数字阵列 , 比最小值 小 ,就更新最小值 。
比最大值 大 ,就更新 最大值 。

所以 每个数字 都要跟 最小和最大值 比较 ,比较次数 是 2n

程序里的比较次数是 1 + 2(n-2) , 第0项和第1项比较1次 ,其余比较两次

第二种方法,递回

写成递回了 , 很像merge sort的写法 。
分成 两个两个 比较 , 比较小的min 更新 最小值 ,比较大的 max 更新最大值
https://ithelp.ithome.com.tw/upload/images/20201020/201119942PjtRi4Xeo.png

比较次数: T(n) = 3n/2 -2
不懂这个方法。
有点像:
关於 selection trees
https://www.youtube.com/watch?v=8d-rn6ZQy6U&ab_channel=%E6%B4%AA%C3%82ng%E6%98%A5%E7%94%B7Chhun-L%C3%A2m

第三种方法,回圈

第三种写法,比较直觉:
回圈 不是一个一个跑 ,而是 i += 2。
先比较 两个数字的大小 ,在跟 最大最小值在比较一次 。
https://ithelp.ithome.com.tw/upload/images/20201020/20111994xADuzqKC0V.png

https://ithelp.ithome.com.tw/upload/images/20201020/20111994zA0h6yYXza.png

https://ithelp.ithome.com.tw/upload/images/20201020/20111994uJ3oKUwbX5.png

阵列有几个数字:

1 个数字 -- >比较 0次

2 个数字 -- >比较 1次

3 个数字 -- >比较 3次 ,因为假如是123 ,会23比较一次 ,2跟最小值(1)在比一次,3跟最大值(1)在比一次

4 个数字 -- >比较 4次 ,因为假如是1234 ,12先比较一次确认最小最大初始值 ,3跟4比谁大谁小一次,4跟最大值2比一次,3跟最小值1比一次 。所以 1+1+1+1 =4次

5 个数字 -- >比较 6次 ,3+3 =6
 If n is odd:    3 * (n-1)/2    (n是奇数13579)(每两个数字比较3次,扣掉第一项)
 
 If n is even:   1 Initial comparison for initializing min and max, 
              and 3(n-2)/2 comparisons for rest of the elements  
                     =  1 + 3*(n-2)/2 = 3n/2 -2  (每两个数字比较3次,第一项和第二项比较1次)
第一种方法的比较次数:  1 + 2(n-2)  = 2n-3

第三种方法的比较次数:  3n/2 -2

如果n是6:
第一种方法:9
第三种方法:7

如果n是20:
第一种方法:37
第三种方法:28

如果n是100:
第一种方法:197
第三种方法:148

如果n是1000:
第一种方法:1997
第三种方法:1498

比较次数差不多。一个2倍,一个1.5倍。

<<:  如何替 RxJS 撰写测试 - 一般测试与弹珠图测试方法

>>:  Day35:HTML(32)响应式网站(2)

Day-00 引言

简简单单的开场白 这个系列的文章一开始是没有想到要出生的,但是在因缘际会之下,成为了学校深度学习课程...

[Golang]func的结构与特性整理-Part 2

二、特性 匿名函数 (没有名字的函数) package main import ( "fm...

AE新手必学の三种常用追踪方法01-Day28

经然第28天了,如果没有这个活动我应该也不会每天练习 一样是六指渊的教学:https://www.s...

Day02. 走出户外,来到巨人的脚下-免费注册个BP来玩玩吧!

《荀子》一书的第二十三篇《性恶篇》提到:「坐而言,不如起而力行。」 疫情期间,因公司分流上班,每天都...

[Day 4] SRE - 保持精简的监控

监控 今天来介绍监控的四个黄金讯号、如何简化以及如何维护。 四个黄金讯号 延迟 流量 错误 饱和度 ...