為什么用任何一個基于“比較”的排序算法對 5 個元素進行排序在最壞情況下所需的比較次數至少為 7 次？
1 回答
慕神8447489
TA貢獻1780條經驗 獲得超1個贊
先上結論：基于比較的排序每次進行關鍵字比較的排序的嚴格時間復雜度為Omega(nlog2(n))
原理在于：
基于比較能獲得的信息有限，根據信息熵每次比較能獲得兩個數之間的關系
而對于n個元素的排序，共有n!種排列
故最壞情況需要的比較次數為log2(n!)
——————
另一類原理：
n個數的排列有n!種，
一次比較能從候選中排除一半，
最壞情況下需要log2(n!)次才能得到最終可能的結果
對于5個元素，共5!=120種排列
需要的比較次數為 log2(120) 約等于 6.9，向上取整得到7
添加回答
舉報
0/150
提交
取消