问题是这样的：假设我们有 N 台机器，并且每台机器存储并且可以操作其 N 个元素，那么，我们如何以最低的成本找到所有 N^2 个元素的中位数？
这真的让我很困扰，希望得到你们的答复，谢谢！
对不起，我写得太简单了。存储在每台机器中的元素是随机的，没有顺序。成本包括I/O成本，以及机器之间的通信，RAM，时间也应该考虑一切。我只是想找到最有效的方法来获得中位数。
这些是我想出的一些解决方案：
- 使用外部排序，如合并排序或其他方式，并找到中位数。
- 使用桶排序，根据其值将所有元素划分为 X 个连续的桶，这样我们就可以决定中位数在哪个桶中。扫描存储桶，我们将得到中位数。
- 我认为"算法简介"中 O（N） 算法中的第 k 个数字应该在这里工作吗？
但是，所有这些解决方案仍然需要一台额外的机器来完成这项工作。我想知道是否有一种方法我们只能使用这 N 台机器来获得中位数？
谢谢！
您需要有一个计算所有值（所有商店的总计）的过程。 选择中间索引。 将索引调整为相应计算机上项目开头的偏移量。 要求该计算机对项目进行排序并返回该索引的值。
Step 1: Sort the numbers at each machine individually
Step 2: Send the median at each machine to a central place
Step 3: Sort the medians and send it to each machine
Step 4: For each element in the sorted medians calculate the rank at machine level
Step 5: Calculate the rank of each element over all machines (just sum the rank)
Step 6: Find two elements in the sorted medians between which the global median exists
Step 7: For the next iteration consider only elements between those two medians
and repeat the whole thing again
在最坏的情况下，第二次迭代中的所有剩余元素都将在一台机器上。
复杂性：非常确定它是O（nlogn）（即包括腭化它可以是O（n^2logn）
你能估计它而不是准确地得到它吗？
如果是这样，请选择一个常数 K 并将 K 系数多项式拟合到每台机器上的数据，将系数发送到中央机器，该中心机器将它们相加，然后通过
- 对范围内的曲线进行积分以找到曲线下方的区域
- 执行寻根算法以找到将区域分成两半的点。
K 越大，误差就越少。 K 越小，效率就越高。