sim*_*mon 57 algorithm selection median-of-medians
我想在下面的例子中理解"中位数中位数"算法:
我们有45个不同的数字,分为9组,每组5个元素.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
第二步递归,找到中位数的"真实"中位数(50 45 40 35 30 25 20 15 10)即该集合将分为两组:
50 25
45 20
40 15
35 10
30
对这两组进行排序
30 10
35 15
40 20
45 25
50
中位数是40和15(如果数字是偶数我们左中位数)所以返回值是15但是中位数的"真实"中位数(50 45 40 35 30 25 20 15 10)是30,而且有5个元素小于15,远小于30 维基百科中提到的45%
所以T(n) <= T(n/5) + T(7n/10) + O(n)失败了.
顺便说一句,在维基百科的例子中,我得到递归的结果为36.但是,真正的中位数是47.
所以,我认为在某些情况下,这种递归可能不会返回真正的中位数中位数.我想知道我的错误在哪里.
tem*_*def 34
问题在于您要找到中位数的真实中位数的步骤.在您的示例中,您有这些中位数:
50 45 40 35 30 25 20 15 10
此数据集的真实中位数为30,而不是15.您不会通过将组拆分为五个块并取这些中位数的中位数来找到此中位数,而是通过递归调用此较小组中的选择算法.逻辑中的错误是假设通过将上述序列分成两个块来找到该组的中位数
50 45 40 35 30
和
25 20 15 10
然后找到每个块的中位数.相反,中位数算法将在完整数据集上递归调用自身50 45 40 35 30 25 20 15 10.在内部,这会将组拆分为五个块并对它们进行排序等,但它确定了分区步骤的分区点,并且在此分区步骤中,递归调用将找到中位数的真实中位数在这种情况下,如果你使用30作为原始算法中的分区步骤,你确实可以根据需要进行非常好的分割.
希望这可以帮助!
sul*_*ing 28
这是中位数算法的伪代码算法(略微修改以适合您的示例).维基百科中的伪代码无法描述selectIdx函数调用的内部工作方式.
我在代码中添加了注释以供解释.
// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. first select call might look like:
// select (array, N/2), where 'array' is an array of numbers of length N
select(L,k)
{
if (L has 5 or fewer elements) {
sort L
return the element in the kth position
}
partition L into subsets S[i] of five elements each
(there will be n/5 subsets total).
for (i = 1 to n/5) do
x[i] = select(S[i],3)
M = select({x[i]}, n/10)
// The code to follow ensures that even if M turns out to be the
// smallest/largest value in the array, we'll get the kth smallest
// element in the array
// Partition array into three groups based on their value as
// compared to median M
partition L into L1<M, L2=M, L3>M
// Compare the expected median position k with length of first array L1
// Run recursive select over the array L1 if k is less than length
// of array L1
if (k <= length(L1))
return select(L1,k)
// Check if k falls in L3 array. Recurse accordingly
else if (k > length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
// Simply return M since k falls in L2
else return M
}
举个例子:
中位数函数的中位数将调用45个元素的整个数组,如(with k = 45/2 = 22):
median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2)
第一次M = select({x[i]}, n/10)调用时,数组{x[i]}将包含以下数字:50 45 40 35 30 20 15 10.在这个调用中,n = 45因此select函数调用将是M = select({50 45 40 35 30 20 15 10}, 4)
第二次M = select({x[i]}, n/10)调用时,数组{x[i]}将包含以下数字:40 20.在这个电话中,n = 9因此呼叫将是M = select({40 20}, 0).此选择调用将返回并分配值M = 20.
现在,来到这里你有疑问的地步,我们现在的阵列分区L周围M = 20用k = 4.
记住L这里的数组是:50 45 40 35 30 20 15 10.
阵列将被划分成L1, L2并且L3根据规则L1 < M,L2 = M和L3 > M.因此:
L1: 10 15
L2: 20
L3: 30 35 40 45 50
因为k = 4,它大于length(L1) + length(L2) = 3.因此,搜索将继续进行以下递归调用:
return select(L3,k-length(L1)-length(L2))
转换为:
return select({30 35 40 45 50}, 1)
结果将返回30.(因为L有5个或更少的元素,因此它将返回kth中的元素,即排序数组中的第1个位置,即30).
现在,M = 30将在第一接收select函数调用45个元件的整个阵列,并且该阵列隔开相同的分区的逻辑超过L周围M = 30将适用于最终得到的中位数的中值.
唷!我希望我的冗长和清晰足以解释中位数算法的中位数.