最小值和最大值 口同时找最小值和最大值 )记录比较过程中遇到的最小值和最大值; 2)成对处理元素,先比较两个输入元素,把较小者与当前最小值比较 ,较大者与当前最大值比较(每对元素需要3次比较) MAX-MINIMUM (A) 1 if length al is odd 2 then min←A[l;max←min; 3 else min MIN(A1, A2)), max+ MAX(A1, A2); 5 while is length min MN( MN(AG, Ali+lD, min max MAX( MAX(Ail, Ai+lD, max 9 end 10 return min, max 2021/1/26
最小值和最大值 同时找最小值和最大值 1）记录比较过程中遇到的最小值和最大值； 2）成对处理元素，先比较两个输入元素，把较小者与当前最小值比较 ，较大者与当前最大值比较（每对元素需要3次比较） 2021/1/26 7 MAX-MINIMUM ( A ) 1 if length[A] is odd 2 then min ← A[1]; max ← min; 3 else min ← MIN( A[1], A[2] ), max ← MAX( A[1], A[2] ); 4 i ++; 5 while i ≤ length[A] 6 min ← MIN( MIN(A[i], A[i+1]), min ) 7 max ← MAX( MAX(A[i], A[i+1]), max ) 8 i ← i+2; 9 end 10 return min, max
最小值和最大值 》如何设定当前最小值和最大值的初始值:依赖于n的奇偶性 如果n是奇数,将最小值和最大值都设为第一个元素的值; 如果n是偶数,就对前两个元素做一次比较,以决定最小值和最大值 的初始值。 总的比较次数: 口如果n是奇数,那么总共做了3n/2次比较 口如果n是偶数,总共做了3n/2-2次比较。 时间复杂度为:O(m) 2021/1/26
最小值和最大值 ➢ 如何设定当前最小值和最大值的初始值：依赖于n的奇偶性 ➢ 如果n是奇数，将最小值和最大值都设为第一个元素的值； ➢ 如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值 的初始值。 ➢ 总的比较次数： 如果n是奇数，那么总共做了 次比较 如果n是偶数，总共做了 次比较。 2021/1/26 8 3n / 2 3n / 2 − 2 时间复杂度为：O(n)
第七讲顺序统计学 内容提要 口最小值和最大值 口以期望线性时间做选择 口最坏情况线性时间的选择 2021/1/26
2021/1/26 9 第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择