我知道中位数算法的中位数公式是：
T(n)<= T(0.7n)+T(0.2n)+O(n)并且O(n)来自于找到每个块的中位数（大小为 5），我想知道为什么需要 O(n) 才能找到每个块的中位数.. 听起来像找到一个块的中位数需要O(1). 这怎么可能？
问问题
80 次
1 回答
0
每个块的大小是恒定的 ( 5)。因此，找到每个块的中位数在O(1)（将块排序O(1)并以中间索引作为中位数）。因此，找到所有块的中位数在O(n). 然后找到在您的另一个问题中回答的每个块的中位数的中位数。
于 2018-10-15T10:03:32.390 回答