修改快速排序的时间复杂度
Time complexity for modification on quicksort
让名为 QUARTERSORT 的函数获取数组并按以下方式对其进行排序：
- 如果
n<100` 它使用常规的 QUICKSORT
- 否则，我们将数组拆分为
A1 = A[1,...,n/4] 和 A2 = A[(n/4)+1,...,n].
- 然后，我们调用 QUARTERSORT 两次：
B1 = QUARTERSORT(A1) 和 B2 = QUARTERSORT(A2)。
- 最后，我们合并
B1 和 B2。
现在，为什么重复是 T(n) = T(0.25n) + T(0.75n) + O(n) 而不是 T(n) = T(0.25n) + T(0.75n) + O(nlogn)？
递归是T(n) = T(0.25n) + T(0.75n) + O(n)，因为算法的每一步都是O(n)。将数组拆分为 2 部分是 O(n)，合并两部分是 O(n)，因此每一步都是 O(n)，这给了我们预期的总数 T(n) = T(0.25n) + T(0.75n) + O(n) .
直觉上，你可以忽略关于快速排序的部分，因为它只发生在小 n 上，而大 O 表示法只讨论 n 的值 "big enough" .所以算法的部分是：
- 对 1/4 输入的递归调用：
T(1/4 * n)
- 递归调用 3/4 输入：
T(3/4 * n)
- 合并：
O(n)
更正式一点：快速排序的时间复杂度是O(1)。这个加法可以忽略不计，因为时间复杂度上还有更大的部分，比如O(n).
快速排序需要 O(n) 才能找到主元。一旦找到枢轴，它就保持不变。
2个子问题的大小分别为O(N/4)和O(3N/4)，所以递归为
T(n) = T(0.25n) + T(0.75n) + O(n)
让名为 QUARTERSORT 的函数获取数组并按以下方式对其进行排序：
- 如果
n<100` 它使用常规的 QUICKSORT - 否则，我们将数组拆分为
A1 = A[1,...,n/4]和A2 = A[(n/4)+1,...,n]. - 然后，我们调用 QUARTERSORT 两次：
B1 = QUARTERSORT(A1)和B2 = QUARTERSORT(A2)。 - 最后，我们合并
B1和B2。
现在，为什么重复是 T(n) = T(0.25n) + T(0.75n) + O(n) 而不是 T(n) = T(0.25n) + T(0.75n) + O(nlogn)？
递归是T(n) = T(0.25n) + T(0.75n) + O(n)，因为算法的每一步都是O(n)。将数组拆分为 2 部分是 O(n)，合并两部分是 O(n)，因此每一步都是 O(n)，这给了我们预期的总数 T(n) = T(0.25n) + T(0.75n) + O(n) .
直觉上，你可以忽略关于快速排序的部分，因为它只发生在小 n 上，而大 O 表示法只讨论 n 的值 "big enough" .所以算法的部分是：
- 对 1/4 输入的递归调用：
T(1/4 * n) - 递归调用 3/4 输入：
T(3/4 * n) - 合并：
O(n)
更正式一点：快速排序的时间复杂度是O(1)。这个加法可以忽略不计，因为时间复杂度上还有更大的部分，比如O(n).
快速排序需要 O(n) 才能找到主元。一旦找到枢轴，它就保持不变。
2个子问题的大小分别为O(N/4)和O(3N/4)，所以递归为
T(n) = T(0.25n) + T(0.75n) + O(n)