1樓：仰綺彤雙秉
分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞迴地解這些子問題，然後將各個子問題的解合併得到原問題的解。它的一般的演算法設計模式如下：
divide-and-conquer(p)
其中，|p|表示問題p的規模。n0為一閥值，表示當問題p的規模不超過n0時，問題已容易解出，不必再繼續分解。adhoc(p)是該分治法中的基本子演算法，用於直接解小規模的問題p。
當p的規模不超過n0時，直接演算法adhoc(p)求解。演算法merge(y1,y2,...,yk)是該分治法中的合併子演算法，用於將p的子問題p1,p2,...
,pk的解y1,y2,...,yk合併為p的解。
根據分治法的分割原則，應把原問題分為多少個子問題才比較適宜？每個子問題是否規模相同或怎樣才為適當？這些問題很難給予肯定的回答。
但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。
這種使子問題規模大致相等的做法是出自一種平衡(banlancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
從分治法的一般設計模式可以看出，用它設計出的演算法一般是遞迴演算法。因此，分治法的計算效率通常可以用遞迴方程來進行分析。一個分治法將規模為n的問題分成m個規模為n/m的子問題，其中k(k<=m)個子問題需要求解。
為方便起見，設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。另外再設將原問題分解為k個問題以及用merge將k個子問題的解合併為原問題的解需用f(n)個單位時間。如果用t(n)表示該分治法divide-and-conquer(p)解規模為|p|=n的問題所需的計算時間，則有：
下面來討論如何解這個與分治法有密切關係的遞迴方程。通常可以用遞迴式的方法來解這類遞迴方程，反覆代入求解得：
注意，遞迴方程及其解只給出n等於m的方冪時t(n)的值，但是如果t(n)足夠平滑，由n等於m的方冪時t(n)的值估計t(n)的增長速度。通常，可以假定t(n)單調上升。
另一個需要注意的問題是，在分析分治法的計算效率是，通常得到的是遞迴不等式：
在討論最壞情況下的計算時間複雜度，用等號(=)還是用小於等於號(<=)是沒有本質區別的。
分治演算法和動態規劃有什麼不同和聯絡？
2樓：軍天下
1. 分治法與動態規劃主要共同點:
二者都要求原問題具有最優子結構性質,都是將原問題分而治之,分解成若干個規模較小(小到很容易解決的程式)的子問題.然後將子問題的解合併,形成原問題的解.
2. 分治法與動態規劃實現方法:
① 分治法通常利用遞迴求解.
② 動態規劃通常利用迭代法自底向上求解,但也能用具有記憶功能的遞迴法自頂向下求解.
3. 分治法與動態規劃主要區別:
① 分治法將分解後的子問題看成相互獨立的.
② 動態規劃將分解後的子問題理解為相互間有聯絡,有重疊部分.
資料結構課程中分治法的基本思想是什麼啊
3樓：匿名使用者
任何一個可以用計bai算機du求解的問題所需的計算時間都與zhi其規模n有關。問題的dao規內
模越小，越容易直接求容
解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。
要想直接解決一個規模較大的問題，有時是相當困難的。
分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
如果原問題可分割成k個子問題（1 這自然導致遞迴過程的產生。分治與遞迴像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。 比較「分治法」和「動態規劃法」的異同點和優缺點 4樓：love小飛龍 共同點：bai 將待求解的問du題分解成若干zhi 子問題，先求dao解子問題 ，然後再從這些子回問題的答解得到原問題的解。 不同點： 1、適合於用動態規劃法求解的問題，分解得到的各子問題往往不是相互獨立的； 而分治法中子問題相互獨立。 2、動態規劃法用表儲存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間複雜度，效率較高； 而分治法中對於每次出現的子問題均求解，導致同樣的子問題被反覆求解，故產生指數增長的時間複雜度，效率較低。 5樓：必勝雙子 /*簡單演算法: **v[0]不儲存資料 **t(n)=o(n^2). */ int maxsum(int *v,int n,int *besti,int *bestj) { int su 普通最小二乘法是一種數學優化技術。它通過最小化誤差的平方和尋找資料的最佳函式匹配。利用最小二乘法可以簡便地求得未知的資料，並使得這些求得的資料與實際資料之間誤差的平方和為最小。x x平 y y平 xy x平y xy平 x平y平 xy x平 y y平 x nx平y平 xy nx平y平 nx平y平 nx... 1.shell排序 shellsort shell排序通過將資料分成不同的組，先對每一組進行排序，然後再對所有的元素進行一次插入排序，以減少資料交換和移動的次數。平均效率是o nlogn 其中分組的合理性會對演算法產生重要的影響。現在多用d.e.knuth的分組方法。shell排序比氣泡排序快5倍，... l這個頭結點是不儲存資料的，l next l的下個結點才儲存資料，為實際的第一個結點 s next l next 新插入的結點s放在第一個結點前面，變為新的第一個結點，l next s 這句讓l next指向新的第一個結點 l next改為l s next l l s可以，這樣頭指標就是實際儲存資料...計量經濟學中，簡述普通最小二乘法的基本思想
C語言資料結構中的幾種內部排序法，求解！高手速度來指導我
c語言資料結構，單連結串列中的頭插法求解釋