中值算法递归关系的中值
Median of median algorithm recurrence relation
我知道线性select（median of medians算法）递归方程如下：
T(n) <= an + T(n/5) + T(7n/10)
但是这些术语是从哪里来的呢？我一直在努力理解，但我非常困惑。谁能解释一下？
最佳尝试：
该等式仅适用于计算 5 组中位数的情况。否则它会发生变化。等式的一部分是算法遍历所有元素并将它们分成 5 组所需的时间。T(n/5) 是找到每组元素的中位数所需的时间5. 因为有 n/5 组 5.
T(7n/10) 需要更多时间...
当你做中位数的中位数时，元素被分成 4 个象限。 3/10 的元素大于中位数的中位数，3/10 的元素小于中位数的中位数。其他 4/10 分成 2 组 2/10。这些是您不确定它们是否大于或小于中位数的元素。因此，大于或小于中位数的元素的最大数量为 3/10 + 2/10 + 2/10 = 7/10。所以 T(7n/10) 是继续等式的一部分，其中最大数字段 larger/smaller 比中位数的中位数....
希望这是有道理的。
我知道线性select（median of medians算法）递归方程如下：
T(n) <= an + T(n/5) + T(7n/10)
但是这些术语是从哪里来的呢？我一直在努力理解，但我非常困惑。谁能解释一下？
最佳尝试：
该等式仅适用于计算 5 组中位数的情况。否则它会发生变化。等式的一部分是算法遍历所有元素并将它们分成 5 组所需的时间。T(n/5) 是找到每组元素的中位数所需的时间5. 因为有 n/5 组 5.
T(7n/10) 需要更多时间...
当你做中位数的中位数时，元素被分成 4 个象限。 3/10 的元素大于中位数的中位数，3/10 的元素小于中位数的中位数。其他 4/10 分成 2 组 2/10。这些是您不确定它们是否大于或小于中位数的元素。因此，大于或小于中位数的元素的最大数量为 3/10 + 2/10 + 2/10 = 7/10。所以 T(7n/10) 是继续等式的一部分，其中最大数字段 larger/smaller 比中位数的中位数....
希望这是有道理的。