算法第二章實踐作業

描述找第k小的數的分治算法（自然語言）
（1）選基準：從數組里隨機挑一個數當作基準值（比如第一個或最后一個元素，比較好的是從第一個，中間那個和最后的選出數值大小居中的）。
（2）分區：把數組分成三部分，比基準小的（左區），等于基準的（中區），比基準大的（右區）。
（3）判斷遞歸（直接返回）：如果中區的下標等于k，那么中區值，即基準值，就是第k小數（直接返回）。如果不然，看第k小數落在哪個區，左區長度>=k，就去左區找第k小數，否則去右區找第k小的數（遞歸搜索）。
分析該算法的最好時間復雜度和最壞時間復雜度
（1）最好時間復雜度：O(n)。每次分區都能均分數組，且只遍歷當前數組O(n)，但遞歸只需走左/右區其中一塊，遞歸層數僅logn，T(n)=n+n/2+n/4+...=O(n)。
（2）最壞時間復雜度：O(n^2)。每次選的基準是數組最值，分區仍遍歷O(n)，但遞歸要走n層（每層只排除 1 個最值元素），T(n)=n+(n-1)+(n-2)+...+1=O(n^2)。
結合本章的學習，談談你對分治法的體會和思考
分治法的核心是 “分而治之”，簡而言之就是“拆大問題->解小問題->合并答案”，不過得保證拆出來的小問題和原問題是一個類型的。其次，并非所有問題都要復雜的合并步驟，比如找第k小數，分區后只需要遞歸一半，也不用合并左右結果，而像歸并排序才需明確合并兩個有序子數組。這說明分治法的關鍵是“分”，“治”要按實際需求操作。另外，拆分的策略決定了效率上限，失敗的策略反而會增加復雜度。總而言之，對于復雜問題（如歸并排序、漢諾塔），分治法能將邏輯拆解為 “拆分-求解-合并” 三步走，降低代碼編寫難度，便于理解和維護。

posted on 2025-10-24 13:01 paidaxing* 閱讀(4) 評論(0) 收藏舉報

刷新頁面返回頂部