分治策略
一、分治策略的基本思想
- 將原始問題劃分為規模較小的子問題，
- 迭代或者遞回求解每一個子問題，
- 將子問題的解綜合得到原問題的解，
注意：
- 子問題與原問題性質一致，
- 子問題相互獨立求解，
- 迭代或遞回停止時子問題直接求解，
二、二分查找
1、核心用法
演算法核心用法：查找一個數x是否在一組數中，下面我們來看一段偽代碼：
輸入一個陣列T，下標從a到b，輸入一個陣列x，若x在陣列T中，輸出下表j，否則輸出0，
依據分治策略的基本思想，我們需要對T進行劃分，使得問題規模變小，因為我們將T對半劃分 (a+b)/2 向下取整，得到陣列的中位數下標m，如果此時x正好是我們找到的中位數m，則輸出下標m，如果x比中位數小，則轉變為在前半個陣列中查找，否則在后半個陣列中查找，一直迭代到查找到數x，則輸出對應下標，否則輸出0，
2、設計思想
- 將數x與中位數進行比較，將原問題轉化為規模減半的子問題，若x小于中位數，則子問題在前半個陣列查找，否則在后半個陣列中查找，
- 對子問題繼續進行二分查找，
- 當子問題規模為1時，直接比較數(x)和T(m),相等則回傳值m，否則回傳0，
顯然，二分查找是一種典型的采用分治策略設計思想的演算法，
3、二分查找的時間復雜度分析
最好的情況下：只需進行一次查找就能得到我們想要的結果，
最壞的情況下：
w(n)=w[n/2]+1 可解為：w(n)=[logn]+1（n為log的下標）
三、歸并排序
1.核心思想
歸并排序：將一組無序的元素按照從小到大進行排序，下面我們來看一段偽代碼：
首先將陣列對半劃分，歸結為兩個子陣列之后進行排序，然后將兩個子陣列重復劃分，排序，最后綜合得到一個從小到大排序的陣列，
2.設計思想
- 將原問題劃分為規模為n/2的兩個子問題，
- 繼續劃分，將原問題劃分成規模為n/4的四個子問題，直到子問題規模為1時，劃分結束，
- 從規模1到規模n/2，陸續歸并排好序的兩個子陣列，歸并一次陣列擴大一倍，直到達到原陣列規模，
3.歸并排序的時間復雜度分析
最好情況陣列本來就是按照順序進行排列的，這時我們不需要進行排序，
w(1)=0
最壞情況下：
w(n)=2w(n/2)+n-1 可解為：w(n)=nlogn-(n+1)
四、總結
- 將原問題規約為規模小的子問題，子問題與原問題具有相同的性質，
- 子問題規模足夠小時可直接求解，
- 演算法可以遞回實作也可以迭代實作，
- 可以使用遞推方程式分析演算法的時間復雜度，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/393125.html
標籤：java
上一篇：Java語言中的運算子