如何理解分治范式中a≥1及子问题大小为n/b的设定？

疑问1：a=1时拆分出的子问题是不是原问题？ #

当然不是。这里的关键是b>1，所以n/b一定小于n，子问题的规模是严格缩小的。a=1的意思是每次拆分后，只需要处理其中1个规模为n/b的子问题，而非所有拆分出的子问题。

举个最典型的例子：二分查找。原问题是在n个元素的有序数组中找目标值，我们把数组拆成左右两个各n/2规模的部分（b=2），然后根据目标值和中间元素的大小关系，只需要处理其中1个部分（a=1）。这时候子问题的规模是n/2，明显比原问题小，完全不是同一个问题。

这种a=1的分治也常被称为「减治法」，核心是通过每次缩小问题规模来逐步逼近解，和拆分成多个子问题并行处理的经典分治（比如归并排序a=2）只是处理方式不同，本质都符合分治范式的定义。

疑问2：为什么子问题大小是n/b而非n/a？ #

这是因为a和b描述的是分治过程中两个独立的维度：

• b是问题拆分的比例：表示把原问题拆成规模为原问题1/b大小的若干份（比如b=2就是拆成两半，b=3就是拆成三等份）。
• a是需要处理的子问题数量：表示拆分后，我们需要递归求解其中a份，而非所有拆分出的子问题。

如果强行用n/a来表示子问题大小，就默认了「拆成a个等规模子问题且全部处理」，但分治的场景远不止这种情况：

• 比如有些问题会把原问题拆成3份（b=3），但只需要处理其中2份（a=2），这时候子问题大小是n/3，而非n/2。
• 再比如二分查找，拆成2份（b=2），只处理1份（a=1），子问题大小是n/2，而非n/1。

用n/b的定义可以更灵活地覆盖所有分治场景，不管是处理全部子问题还是部分子问题，都能准确描述子问题的规模。

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