作者SELAHAPPOP (Let's Go Yankees)
看板TransCSI
标题[问题] 快速排序法的比较问题
时间Fri Jul 4 11:51:54 2008
假设使用快速排序法将16个数字排序
最差的情况下须要几次比较?
答案是120次
我原本的想法是直接拿o(n^2)下去做 後来发现是错的.....
请问各位前辈该如何解这题呢??
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.127.245.213
1F：推 future1234:基本上那个O(n^2)还包括pivot key位置的选择,比较次数 07/04 19:10
2F：→ future1234:导出来, upper-bound的T(n) = O(n^2) 07/04 19:10
3F：→ future1234:所以最差比较次数 " n(n-1)/2 " ,代下去 07/04 19:11
4F：→ SELAHAPPOP:Thx!!! 07/06 18:38