判断题
偏易
#19751
快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pivot)的方法完全避免退化。
快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pivot)的方法完全避免退化。
答案与解析
正确答案:错
解析
快速排序的时间复杂度取决于递归划分的平衡性。每次划分由基准值的选择决定,若基准值始终为最大或最小元素,将导致每层仅减少一个元素,形成n层递归,每层处理n、n-1、…个元素,时间复杂度为O(n²)。随机化选择基准值可改变划分结果的概率分布,使最坏情况发生的概率降低,但无法排除所有非均衡划分的可能性。因此,随机化影响划分的期望平衡性,不保证每次递归深度为O(log n)。算法复杂度分析包含最坏、平均与最好情况,随机化改变的是期望性能而非最坏情况的理论上界。