面试常见算法

分治策略，古已有之，秦朝“连横”策略即为其应用。在计算机领域，这一策略被广泛应用在问题解决中，通过将大问题分解为小规模同类问题，逐步解决并合并答案。递归是实现分治法的关键，如归并排序，将问题划分为两半，递归排序后再合并，其时间复杂度为[公式]。归并排序代码显示了递归“分”和合并“治”的过程。

另一种变体是减治法，如欧几里得算法求最大公约数，通过问题规模减小直至找到答案。二分查找也是减治法的体现，通过不断缩小搜索范围，最终找到目标。快速排序以枢轴划分数据，每次划分减小问题规模，Python实现简洁，但枢轴选择对效率有直接影响。为优化空间开销，可采用原地排序。

快速排序是分治法的一个实例，但因其与枢轴相关，有时也归为减治法讨论。TopK问题的解决方法，如随机选择算法，也是利用快速排序的划分思想，通过一次划分找到前K大数，时间复杂度为[公式]。总的来说，分治法和减治法在面试算法题中常见，如找中位数、最近点对等，它们通过分解和合并策略，简化复杂问题。