algorithm - Recurrence Relation for Deterministic Selection Algorithm

Question

Linear time deterministic algorithm exists for selection. I read this link and the recurrence for a divide and conquer approach looks like: T(n) <= 12n/5 + T(n/5) + T(7n/10)

However, I don't understand why must it be T(7n/10). The link itself has mentioned that each half of the partition has size (3n/10), so the algorithm recurses on (6n/10). Even if we include the 5 elements from the group of the median of medians, the recursion is on (6n/10+5). I do understand that 7n/10 is a valid upper bound on the size of the recursion, but isn't it too weak an upper bound here?

Answer 1

7n/10不是3n/10 + 3n/10 + n/10;的结果 它来自于做n - 3n/10。

从链接：

就丢弃的元素（不包括在调用中）而言，谈论这个更容易。

论点是递归调用是在不包含某些元素而形成的较短列表上进行的。通过显示至少 3n/10元素被排除在列表之外，因此最多 7n/10包含元素，并且该边界是紧密的，因为该3n/10边界是紧密的。

3n/10因此，通过显示 L1 和 L3 至少包含来自每个子集的至少 3 个元素，这表明 L1 和 L3 都具有大小n/10；然后从递归调用中排除 L1 或 L3 之一，给出结果。由于只排除了 L1 或 L3 中的一个 - 而不是两者 - 将它们的大小加在一起是没有意义的。