作者CindyLinz (Cindy Wang)
看板CSSE
标题Re: [问题] 资料结构 快速排序的最差情形
时间Sun Jun 19 19:13:43 2011
※ 引述《eric80520 (freejustice)》之铭言：
: 题目是使用快速排序的时候
: 什麽时候会产生最差情形
: 试证明你的答案
: 我大概知道最差情形是整个资料是
: 由大到小依序排好的资料
: 但是要怎麽证明
: 最差情形的C(n,2)=n(n-1)/2 为O(n^2)
: 又是怎麽来的呢?
: 谢谢
n(n-1)/2 = 0.5n^2 - 0.5n
0.5n^2 - 0.5n < 0.5 n^2 ∀ n>=1
0.5 是个常数..
这样就可以了 :Q
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 210.242.246.249
※ 编辑: CindyLinz 来自: 210.242.246.249 (09/10 13:14)