如何通过时间复杂度递推式判断算法设计模式及减治分治差异

注：T(n)为递推关系

若输入规模为n的算法时间复杂度定义如下：
T(1)=A
当n>1时，T(n)=T(n-1)+B
其中A和B均为正的常数值。
则该算法采用的设计模式最准确的描述是： #

A. Decrease and Conquer（减治法）——正确答案
B. Divide and Conquer（分治法）
C. Quadratic（平方级时间复杂度）
D. Generate and Test（生成测试法）

对递推式展开求解可得T(n) = nB + A，对应时间复杂度为O(n)。

1. 减治法与分治法的核心区别 #

两者都属于通过缩小问题规模求解原问题的算法设计思路，核心差异在子问题的数量和处理逻辑上：

• 分治法会将规模为n的原问题拆分为至少2个互相独立的、规模更小的同构子问题，递归求解所有子问题后，还需要额外的合并步骤把多个子问题的结果组合成原问题的解。它的递推式通用形式为T(n) = a*T(n/b) + f(n)，其中a≥2，代表拆分出的子问题总数。典型代表是归并排序、快速排序、大整数乘法类算法。
• 减治法每次只会将原问题缩减为1个规模更小的同构子问题，不需要处理多份子问题，也不存在多结果合并的步骤，只需要在规模缩减的过程中完成固定量的操作，就能从子问题的解直接得到原问题的解。它的递推式通用形式为T(n) = T(n-k) + f(n)（常数规模缩减，比如每次减1）或T(n) = T(n/k) + f(n)（比例规模缩减，比如每次规模减半），永远只有1个递归项。典型代表是插入排序、顺序查找、阶乘计算、欧几里得求最大公约数。

2. 本题选减治法的原因 #

• 首先看递推式匹配度：题目给出的T(n) = T(n-1) + B，每次递归仅调用1次规模为n-1的子问题，B对应当前步骤的常数级处理开销，完全符合减治法“单一大规模子问题+常数时间递推”的特征，属于最典型的减常数规模类减治算法，和阶乘计算、插入排序的递推结构完全一致。
• 其余选项可直接排除：
  • 分治法要求拆分出至少2个独立子问题，本题递推式仅1个递归项，不满足分治的核心特征。
  • 平方级复杂度对应O(n²)的时间开销，本题求解得到复杂度为线性O(n)，描述本身错误，且题目问的是算法设计模式，不是复杂度类别，答非所问。
  • 生成测试法的核心逻辑是枚举所有可能候选、逐一校验是否符合要求，递推逻辑和本题完全不匹配。

内容的提问来源于stack exchange，提问作者Freddy Mcloughlan