全部文章

页码6/11

活动选择问题

给定 n 个互斥占用同一资源的活动，每个活动包含指定的开始时间与结束时间，要求在所有活动中挑选出一个互不冲突且数量最多的活动集合。

贪心算法是一种在每步决策中均采取当前局部最优选择的策略，其核心在于满足贪心选择与最优子结构性质，以极低的时间复杂度求解全局最优解，但需注意在不满足性质时容易陷入无法回溯的局部最优陷阱。

分治法是一种算法设计思想，其核心在于将复杂的大问题分解为若干结构相同且相互独立的微型子问题，通过递归求解各子问题后再将其解合并，从而高效得出原问题的解。

递归是一种通过函数调用自身来解决问题的编程技巧，其核心在于具备终止条件与递归步骤，通过将大问题拆解为规模更小的子问题逐步求解，但也需注意避免因重复计算导致的性能陷阱。

穷举搜索（暴力搜索）是一种通过无遗漏地列举并检验解空间中的每一个候选解，以算力换取解法正确性的基础计算机求解策略。

桶排序将数据按数值范围划分到若干个桶内，每个桶内部再使用其他排序算法排序，最后依次合并所有桶的元素得到有序序列；平均时间复杂度 O(n)，适合数据分布均匀的场景，需要额外开辟桶空间，属于稳定排序。

快速幂取模通过二进制拆分指数，将大指数幂运算的时间复杂度降至 O (log n)，在每一步运算中同步做取模操作，避免数值溢出，用来高效求解 a 的 b 次方对 m 取模的结果。

快速幂借助指数的二进制拆分，把 a 的 b 次方的时间复杂度从 O (b) 优化到 O (log b)。不断对底数平方，当指数二进制位为 1 时就把当前底数乘入答案，常搭配取模处理大数，高效计算大指数的模值。