来自 https://en.wikipedia.org/wiki/Quickselect它说
“但是,与在快速排序中那样递归到两侧不同,快速选择仅递归到一侧——它正在搜索的元素所在的一侧。这将平均复杂度从 O(n log n) 降低到 O(n ),最坏情况为 O(n^2)。”
我不明白减少到只看一侧如何将平均复杂度降低到 O(n)?不是更多的 O(N/2 log N) 仍然是 O(N log N)。最坏的情况如何 O(n^2)
最佳答案
n log(n)
表示该算法查看所有 N 项 log(n) 次。但这不是 Quickselect 的情况。
假设您正在使用 Quickselect 从 128 项列表中选择前 8 项。由于随机选择的奇迹,您选择的轴心始终位于中间点。
在第一次迭代中,该算法查看所有 128 个项目并将其分成两组,每组 64 个项目。下一次迭代分成两组,每组 32 个项目。然后是16,然后是8。检查的项目数是:
N + N/2 + N/4 + N/8 + N/16
该系列的总和永远不会达到 2*N。
最坏的情况是分区总是导致分区大小非常倾斜。考虑如果第一个分区只删除一个项目会发生什么。而第二个只删除了一个,等等。结果将是:
N + (N-1) + (N-2) ...
也就是 (n^2 + n)/2)
,或者 O(n^2)。
关于algorithm - 快速选择时间复杂度解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56940793/