@chawuciren
2019-02-02T11:26:04.000000Z
字数 1935
阅读 752
未分类
前提:每一个数都不一样
最大最小中位数
加入lower median和upper median,取下界上界之分
常规算法:使用这种算法同时找到最大最小值每个元素比较两次
int minmum(int A[],int length){
min=A[0];
for(int i=1;i<length;i++){
if(min>A[i]) min=A[i];
}
return min;
}
We compare pairs of elements from the input first
with each other, and then we compare the smaller with the current minimum and
the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
这样只要3[n/2] (取下界)
Show that the second smallest of n elements can be found with n C dlg ne 2
comparisons in the worst case. (Hint: Also find the smallest element.)
Prove the lower bound of d3n=2e 2 comparisons in the worst ca
se to find both
the maximum and minimum of n numbers. (Hint: Consider how many numbers
are potentially either the maximum or minimum, and investigate how a comparison
affects these counts.)
分治找到第几个最小值
用到的函数实现在这里
RANDOMIZED-SELECT(A; p; r; i )//i是第几个
if p == r//p、r是左右边界,分到不能分了就返回仅有元素
return A[p]
q=RANDOMIZED-PARTITION(A; p; r)//q是分解的下标
k=q-p+1
if i = = k // the pivot value is the answer
return A[q]
elseif i<k
return RANDOMIZED-SELECT(A; p; q-1; i )
else return RANDOMIZED-SELECT(A; q C 1; r; i-k)
跳证明,以后补
大意是说,先分成n/5组,每组五个元素(最后一组有n%5个)。然后找出每组的中位数,找出这些中位数的中位数,围绕这个中位数分数组(一边全部小于这个数,一边全部大于这个数)。递归直到找到要找的某个最小值。