algorithm - 主定理案例 3 示例算法

Question

在学习Master theorem时，我无法想出一个真实世界的算法作为示例，其递归策略将属于Case 3。您能否建议任何链接，我可以在其中阅读有关此类算法的更多信息？

Answer 1

当执行第一个递归步骤的工作量与所有其他步骤的工作量相当时，就会出现案例 3。用于查找数组中值的快速选择算法就是一个很好的例子。