递归关系的时间复杂度由下式给出:
T(n) = aT(n/b) + f(n) 这里f(n)是征服子问题的代价，即合并的代价
所有子问题都是为了解决问题，但在分区的情况下，我们围绕特定的枢轴点划分数组，因此在计算快速排序的时间复杂度时，为什么我们采用 O(n)
f(n) 的时间。
这是如何作为一个征服的步骤？
最佳答案
不明白你所说的征服一步是什么意思。
f(n) 实际上是在递归函数中所做的任何事情的成本，它发生在递归之前、之后或递归之间。
在快速排序的情况下，合并分区的解的成本为0，因为在枢轴的左右两侧排序后不需要做任何事情。全部成本都在制作分区上，为此，您需要定位您选择的枢轴。这就是为什么快速排序被归类为分而治之的 Hard Split Easy Join 类型。
定位枢轴的成本是O(n)，因为您必须从左到右和从右到左移动，找到枢轴错误一侧的项目，并交换它们, 直到两个搜索(从左到右和从右到左)相互交叉。
希望这有助于您的理解，如果我完全误解了您的问题，我们深表歉意。
关于algorithm - 分区步骤如何作为快速排序中的征服步骤？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34187145/