[課業] 資料結構/搜尋大小第K位

作者: conan77420 (人生就是不停的戰鬥) 看板: Examination
標題: [課業] 資料結構/搜尋大小第K位
時間: Wed May 26 23:40:52 2010


1.考試科目：資料結構


2.章節名稱or篇名(單元關鍵字)：quick sort


3.目前參考用書or考古題出處：高點講義


4.想問的內容：

有一個問題是在一群無排序的數中，如何設計演算法，使找尋第K小的數，只要O(n)

解法是利用quick sort的方式，原本要做兩邊的partition，只做一邊，程式碼如下：

int selectkth(int a[] , int low , int high ,int k)
{
 int mid;

 mid = partition(a,low,high);

 if(mid==k) return(a[mid]);

 else if(k
 else return(selectkth(mid+1,high,k));

}

但是我後來算了一下時間複雜度，好像不是O(n)

T(n)=T(n/2)+cn            //每次做一半的partition，partition用n次

令 n=2^k

T(2^k)     =   T(2^(k-1))+2^(k)-1       //1式
T(2^(k-1)) =   T(2^(k-2))+2^(k-1)-1     //2式

1式-2式*2

T(2^k) - 3T(2^(k-1)) + 2T(2^(k-2)) = 1  //3式

再遞移一次

T(2^(k-1)) - 3T(2^(k-2)) + 2T(2^(k-3)) = 1 //4式

3式-4式

T(2^k) - 4T(2^(k-1)) + 5T(2^(k-2)) - 2T(2^(k-3))=0

換成r

r^3 - 4(r^2) + 5r - 2 = 0

解 r = 1(重根), 2

特徵方程式: 1^n*(C1*n+C2)+2^n*C3

所以看得出來時間複雜度是 O(2^n)

跟原來說的O(n)不符耶！

請問我哪裡算錯了？

不知道我打成這樣大家看不看的懂，自己都覺得很亂@_@

謝謝