[問題] quicksort on peaked array

作者: jb679123 (straw man)   2014-11-02 14:35:40
題目:令T(n)為使用quicksort排序一個peak陣列中n個元素的時間
peak array是指陣列中的元素大小像一個凸峰
ex:1,3,5,7,9,8,6,4,2
假設要排序上面的元素,那T(n)的遞迴是該怎麼寫??
目前知道最佳的情況是T(n)=2T(n)+c.n
最糟的情況是T(n)=T(n-1)+c.n
但像這種情況不知道該怎麼下手..
作者: yr (Sooner Born Sooner Bred)   2014-11-02 18:33:00
問題: 1,2,3,4,5 算 peaked array 嗎

Links booklink

Contact Us: admin [ a t ] ucptt.com