记录学习内容。
以下内容和截图大多引用文章。
还不了解,内容可能有错误。
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 更新最大值
比较次数: 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。
先比较 两个数字的大小 ,在跟 最大最小值在比较一次 。
阵列有几个数字:
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 撰写测试 - 一般测试与弹珠图测试方法
简简单单的开场白 这个系列的文章一开始是没有想到要出生的,但是在因缘际会之下,成为了学校深度学习课程...
二、特性 匿名函数 (没有名字的函数) package main import ( "fm...
经然第28天了,如果没有这个活动我应该也不会每天练习 一样是六指渊的教学:https://www.s...
《荀子》一书的第二十三篇《性恶篇》提到:「坐而言,不如起而力行。」 疫情期间,因公司分流上班,每天都...
监控 今天来介绍监控的四个黄金讯号、如何简化以及如何维护。 四个黄金讯号 延迟 流量 错误 饱和度 ...