快速排序的最大递归深度问题

徐永强 发布于 2014/10/12 22:00
阅读 1K+
收藏 1

一个通过递归实现的快速排序算法。

用于排序的N个元素随机无序生成

每次用于分割子区间的key元素,从当前区间内按平均分布随机获取,

那么该快速排序过程中最大递归深度h的 概率分布是什么样子?

加载中
0
白文
白文
应该是均匀分布,但这种划分不影响时间复杂度,只要是常数比例的划分都会产生深度为O(logn)的递归树,每一层的时间代价者都是O(n),运行总时间为O(nlogn),不太清楚楼主究竟要了解什么
徐永强
徐永强
所以我觉得比较难计算。
白文
白文
回复 @徐永强 : 这个与初始序列及Key在最后有序序列的位置有关,如果经过大量随机初始序列测试和均匀分布的Key,结果应该符合均匀分布。单纯探讨一个例子,结果比较难说。时间复杂度和递归层次受初始序列影响很大,而与Key的选择没什么太大的关系
徐永强
徐永强
log2(N)是最小深度,O( log2(N) )是期望,也有小概率产生较大的深度(甚至达到N),我想知道概率分布是什么样子。是不是很无聊?
返回顶部
顶部