Joh*_*ith 2 quicksort
任何人都可以解释为什么quicksort的最坏情况运行时是O(n ^ 2)以及为什么这很罕见？
Rya*_*n M 7
如果每次以最差的方式选择枢轴,而不是分成两个大小为n/2的列表,则它将分成大小为1和大小为n-1的一个.这导致n的递归深度和总时间n ^ 2.
这是罕见的,因为枢轴通常是随机选择的,因此每次选择最差枢轴的机会很小,平均而言,枢轴将倾向于将列表大致分成两半.
如果非随机选择枢轴,例如取第一个元素,则某些输入(预先排序或反向排序的列表)可以强制执行n ^ 2.
归档时间：
12 年，8 月 前
查看次数：
8651 次
最近记录：