查找一组随机16位数的中位数的检查次数

我们的老师给我们提出了一个问题，通过编程来确定使用决策树查找一组16位随机数的中位数所需的检查次数。他还告诉我们，尽可能少的支票数量是2N，但是当我们在纸上做了27次支票时，我们加倍检查了我们的工作，一切正常。那么他们对于最少数量的支票是一个明确的答案？查找一组随机16位数的中位数的检查次数

来源

2015-01-31 russiandobby

这个问题应该在http://math.stackexchange.com上提问 – Mouser 2015-01-31 19:13:57

与排序数组并找到特定元素不一样吗？ – RE60K 2015-01-31 19:16:01

dam对不起，我完全忘记了数学之一 – russiandobby 2015-01-31 19:19:19

The paper“Samuel W.Bent and John W.Johnson.Definding the median requires 2n comparisons.Proceedings of the 19th Annual ACM Symposium on Computing Theory，pages 213 {216,1985”证明2n是一个下界。

本文需要访问ACM，但在第3页的“ON LOWER BOUNDS FOR SELECTING THE MEDIAN”中有另外的证明可用here。

也许你可以解释你提出的解决方案？

来源

2015-01-31 19:58:41

查找一组随机16位数的中位数的检查次数

回答

相关问题