問題描述

隨機生成含有n個不同元素的數(shù)組L（n≥10000），要求找出第k小的元素（k≤n），完成下面的任務：
（1）設計一個基于排序選擇算法程序，編程調試正確（排序算法自己確定）。
（2）設計一個時間復雜度為O(n)的選擇算法，編程調試正確。
（3）從理論上分析上述兩種算法的時間復雜度，并且通過實際數(shù)據(jù)計算驗證理論分析結果。
（4）寫出實驗報告。

問題分析

1、找出序列中的第k小元素，并將時間復雜度降低到O(n)，我們首先想到的方法是利用排序，比如冒泡排序、選擇排序，只排到第k小就截止，此時時間復雜度應為O(n^2 )，并不符合要求。
2、根據(jù)分治法思想，有如下思路：
對于集合A[1…n]中的元素，用其中某元素V進行劃分:



if ，問題歸結為在A_1中找第k小元素
else if ，V就是第K小元素
else if ，問題歸結為在A_3中尋找第 小元素。
對于第一、三中情況，只需要進行遞歸即可。
3、時間復雜度分析，設T(n)為n元數(shù)組的時間復雜度
最壞情況下:
T(n)=T(n-1)+n-1
解得：T(n)=O(n^2 )
一般情況下：
T(n)=T(n/2)+n-1
解得：T(n)=O(n)

相關代碼

int quickOnce(int *theArray, int left, int right) // 快排的單次劃分過程 {int value = theArray[left];int l = left, r = right;while (l < r){while (l<r && theArray[r]>value)r--;if (l < r){theArray[l] = theArray[r];l++;}while (l < r && theArray[l] < value)l++;if (l < r){theArray[r] = theArray[l];r--;}}theArray[l] = value;return l; }int quickFind(int * theArray, int left, int right, int k) //參數(shù)均為下標 {int index = quickOnce(theArray, left, right); // 執(zhí)行一次劃分操作if (index < k) // |A1|+|A2|<k 情況{return quickFind(theArray, index+1, right, k);}else if (index > k) // |A1|>=k情況{return quickFind(theArray, left, index, k);}else // index正好是分界時{return theArray[index];}}

總結

以上是生活随笔為你收集整理的分治法实验-寻找第k小元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。