首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

大牛过来看看,关于算法导论讲 快排的平均性能分析,该如何解决

2012-02-29 
大牛过来看看,关于算法导论讲 快排的平均性能分析算导上讲快排划分的平衡性时写道,只要按照常数比例划分都

大牛过来看看,关于算法导论讲 快排的平均性能分析
算导上讲快排划分的平衡性时写道,只要按照常数比例划分都是平衡的划分,无论是按1:9,还是1:99。

接着算导上举了个例子,每次按1:9划分,递归树最大高度 h = log(10/9 n) = O(log2n)。

我不明白为什么 log(10/9 n) = O(log2n)



一直对快排为什么能对随机输入的数据那么高效的排序好奇,大家说说自己的见解




[解决办法]
log(10/9 n) = log2(n)/log2(10/9)
1/log2(10/9)是常系数, 时间复杂度是O(log2n)

随机输入的话, 由于数据成正态分布, 每次划分比例接近1:1的数学期望比较高, 常系数会比较小.

热点排行