运行n次Quicksort的整体程序计算复杂度相关问题

结论：该程序的整体时间复杂度不是Θ(nlogn)

原因如下：

• 我们已知的Θ(nlogn)是单次对长度为n的数组执行快速排序的时间复杂度，本题中排序对象是长度为n的数组B，所以每次排序B的时间代价固定为Θ(nlogn)。
• 程序的执行逻辑是：遍历数组A的所有元素，每遍历一个元素就执行一次B的排序，数组A总共有n个元素，所以排序操作总共会执行n次。
• 总时间复杂度为单次排序代价 × 排序执行次数，即 n * Θ(nlogn) = Θ(n²logn)，显然和Θ(nlogn)不属于同一个增长量级。

额外提醒：不要混淆两个n的含义，一个是控制循环执行次数的规模n，一个是排序目标数组的长度规模n，二者是独立的规模参数，计算总复杂度时需要叠加计算。

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