大牛过来看看,关于算法导论讲 快排的平均性能分析
算导上讲快排划分的平衡性时写道,只要按照常数比例划分都是平衡的划分,无论是按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的数学期望比较高, 常系数会比较小.