快速排序分析
Quicksort Analysis
问题：
这是对快速排序的一种修改：只要我们在子列表中有十个或更少的项目，我们就使用选择排序对子列表进行排序，而不是使用快速排序进一步递归。这会改变快速排序的大 O 时间复杂度吗？解释。
在我看来，大 O 时间复杂度会发生变化。我们知道选择排序是 O(n^2)，因此对 10 个或更少项目的子列表进行排序将花费 O(n^2)。在我们得到一个包含十个或更少项目的子列表之前，我们将使用快速排序并继续对列表进行分区。所以最后我们会有 O( nlogn + n^2) 也就是 O(n^2).
我说的对吗？如果不是，有人可以解释为什么吗？
大O复杂度不变。请阅读大师方法（又名大师定理）https://en.wikipedia.org/wiki/Master_theorem
如果您仔细考虑算法，因为排序列表的大小变得异常大，那么对任何给定递归子树中的最后十个进行排序的时间对总体 运行 时间的贡献微不足道。
时间复杂度实际上不受影响的原因是10是常数项。无论整个数组有多大，对大小为 10 或更小的子数组进行排序总是需要一定的时间。如果你正在对一个包含一百万个元素的列表进行排序，那么常数 10 在对列表进行排序所需的实际时间中将扮演非常小的角色（大部分时间将花费在递归地将原始数组划分为子数组）。
如果对包含 10 个元素的列表进行排序需要常数时间，则在每个递归步骤中对数组进行分区是线性的，并且最终得到 log n 个包含 10 个或更少项目的子数组，最终得到 O(n log n + log n)，这与 O(n log n) 相同。
说选择排序是 O(n^2) 意味着算法的 运行 时间随着输入的大小呈二次方增长。 运行 对具有固定数量元素的数组进行选择排序将始终花费固定的时间，但是如果您要比较 运行 对不同大小的数组进行选择排序的时间，您会看到随着输入大小线性变化，运行 时间呈二次方增长。
问题：
这是对快速排序的一种修改：只要我们在子列表中有十个或更少的项目，我们就使用选择排序对子列表进行排序，而不是使用快速排序进一步递归。这会改变快速排序的大 O 时间复杂度吗？解释。
在我看来，大 O 时间复杂度会发生变化。我们知道选择排序是 O(n^2)，因此对 10 个或更少项目的子列表进行排序将花费 O(n^2)。在我们得到一个包含十个或更少项目的子列表之前，我们将使用快速排序并继续对列表进行分区。所以最后我们会有 O( nlogn + n^2) 也就是 O(n^2).
我说的对吗？如果不是，有人可以解释为什么吗？
大O复杂度不变。请阅读大师方法（又名大师定理）https://en.wikipedia.org/wiki/Master_theorem
如果您仔细考虑算法，因为排序列表的大小变得异常大，那么对任何给定递归子树中的最后十个进行排序的时间对总体 运行 时间的贡献微不足道。
时间复杂度实际上不受影响的原因是10是常数项。无论整个数组有多大，对大小为 10 或更小的子数组进行排序总是需要一定的时间。如果你正在对一个包含一百万个元素的列表进行排序，那么常数 10 在对列表进行排序所需的实际时间中将扮演非常小的角色（大部分时间将花费在递归地将原始数组划分为子数组）。
如果对包含 10 个元素的列表进行排序需要常数时间，则在每个递归步骤中对数组进行分区是线性的，并且最终得到 log n 个包含 10 个或更少项目的子数组，最终得到 O(n log n + log n)，这与 O(n log n) 相同。
说选择排序是 O(n^2) 意味着算法的 运行 时间随着输入的大小呈二次方增长。 运行 对具有固定数量元素的数组进行选择排序将始终花费固定的时间，但是如果您要比较 运行 对不同大小的数组进行选择排序的时间，您会看到随着输入大小线性变化，运行 时间呈二次方增长。