分治法的演算法復雜度

㈠ 多項式乘法分治演算法的時間復雜度怎樣計算

長度為2n的多項式，可以分解為3次長度為n的乘法
運行時間
T(n)=3*T(n/2)
可以得復雜度為N^(log3）

我是說的兩個n項的多項式，還有另一種快速傅里葉變換的演算法，復雜度是（N*log(N))

㈡ 比較「分治法」和「動態規劃法」的異同點和優缺點

共同點：
將待求解的問題分解成若乾子問題，先求解子問題，然後再從這些子問題的解得到原問題的解。
不同點：
1、適合於用動態規劃法求解的問題，分解得到的各子問題往往不是相互獨立的；
而分治法中子問題相互獨立。
2、動態規劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高；
而分治法中對於每次出現的子問題均求解，導致同樣的子問題被反復求解，故產生指數增長的時間復雜度，效率較低。

㈢ 快速排序法的平均時間復雜度和最壞時間復雜度分別是多少

快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n^2)。

當排序已經成為基本有序狀態時，快速排序退化為O(n^2)，一般情況下，排序為指數復雜度。

快速排序最差情況遞歸調用棧高度O(n)，平均情況遞歸調用棧高度O(logn)，而不管哪種情況棧的每一層處理時間都是O(n)，所以，平均情況（最佳情況也是平均情況）的時間復雜度O(nlogn)，最差情況的時間復雜度為O(n^2)。

(3)分治法的演算法復雜度擴展閱讀

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序，它採用了一種分治的策略，通常稱其為分治法。快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

（1）首先設定一個分界值，通過該分界值將數組分成左右兩部分。

（2）將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。

（3）然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

（4）重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

㈣ 分治演算法時間復雜度

一：分治演算法和遞歸
1.簡述遞歸

我們要講到分治演算法，我覺得有必要說一下遞歸，他們就像一對孿生兄弟，經常同時應用在演算法設計中，並由此產生許多高效的演算法。
直接或間接的調用自身的演算法稱為遞歸演算法。用函數自身給出定義的函數稱為遞歸函數。

int fibonacci(int n){
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
先簡單看一下經典的遞歸例子，博主會找個時間系統詳細的總結一下關於遞歸的內容。

2.簡述分治

分治法的設計思想是：

分–將問題分解為規模更小的子問題；
治–將這些規模更小的子問題逐個擊破；
合–將已解決的子問題合並，最終得出「母」問題的解；
一個先自頂向下，再自底向上的過程。

凡治眾如治寡，分數是也。—孫子兵法

3.分治法與遞歸的聯系

由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

二：分治法的適用條件
分治法所能解決的問題一般具有以下幾個特徵：

1) 該問題的規模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
3) 利用該問題分解出的子問題的解可以合並為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

第一條特徵是絕大多數問題都可以滿足的，因為問題的復雜性一般是隨著問題規模的增加而增加；

第二條特徵是應用分治法的前提它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；、

第三條是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。

第四條特徵涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好

三：分治法的基本步驟
分解問題：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；（自頂向下）
這里涉及到一個平衡子問題的思想：人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。

解決問題：如果問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題，以得到小問題的解。
合並結果：將各個子問題的解合並為原問題的解：（自底向上）。
它的一般演算法設計模式如下：
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //（2）解決問題：遞歸到小問題，則解決小規模的問題（自頂向下）
divide P into smaller subinstances P1,P2,...,Pk；//（1）分解問題
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //利用遞歸的解各子問題
return merge(y1,...,yk); //將各子問題的解合並為原問題的解（自底向上）
}
四：分治法的復雜性分析
從分治法的一般設計模式可以看出，用他設計出的程序一般是遞歸演算法。因此分治法的計算效率通常可以用遞歸方程來進行分析。
一個分治法將規模為n的問題分成k個規模為n/m的子問題去解。設分解閥值（表示當問題P規模不超過n0時，問題已容易解出，不必再繼續分解）n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合並為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

通常可以用展開遞歸式的方法來解這類遞歸方程，反復帶入求解得

㈤ 分治法能真正提高演算法效率么

樓主可以去對比一下冒泡排序和快速排序（平均性能），這是比較典型的用分治法把復雜度從n^2降低到nlogn的例子。。。
本來是n*n的復雜度，分治後，一共有logn層（想像一下樹的結構，子節點數n的二叉樹有幾層？），每一層內的復雜度還是n，這樣總復雜度就變成了nlogn。大致思路如此。

㈥ 求解一個復雜度排序問題

一般來說, 標準的分治法合並排序時間復雜度為O(n * lg n), 略小於插入排序的O(n*n), 遞歸式的時間復雜度求解方法比較多,有畫圖分析法, 算式求解即類似於 T(n) = f(T(n-1))的求解方法, 還有就是憑經驗猜然後用數學歸納法證明等等, 對於你的問題最直觀的方法就是畫圖法, 這是一個二叉樹問題, 最開始的序列被遞歸地分為兩份, 因此這棵樹的高度為lg n的下取整(這里我們不討論取整的細節), 層數為1 + lg n, 每一層的合並排序代價總和都為c*n(c為某個常數), 因此整棵樹代價為c*n*lg n + c*n, 因此時間復雜度為O(n*lg n);
也可以用他的表達式求解,這個問題的表達式為:T(n)=2*T(n/2)+O(n)
嚴格來講,上面所說的O更好的替代品為theta(符號打不出來,就用這個代替吧,^_^), 具體可以參考一下機械工業出版社的《演算法導論》

㈦ 簡述分治法的基本思想

分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然後將各個子問題的解合並得到原問題的解。它的一般的演算法設計模式如下：
divide-and-conquer(P)
{
if(|P|<=n0)
adhoc(P);
divide
P
into
smaller
subinstances
P1,P2,...,Pk;
for(i=1;i<=k;i++)
yi=divide-and-conquer(Pi);
return
merge(y1,...,yk);
}
其中，|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的問題所需的計算時間，則有：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_002.jpg
下面來討論如何解這個與分治法有密切關系的遞歸方程。通常可以用展開遞歸式的方法來解這類遞歸方程，反復代入求解得：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_001.jpg
注意，遞歸方程及其解只給出n等於m的方冪時T(n)的值，但是如果T(n)足夠平滑，由n等於m的方冪時T(n)的值估計T(n)的增長速度。通常，可以假定T(n)單調上升。
另一個需要注意的問題是，在分析分治法的計算效率是，通常得到的是遞歸不等式：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_000.jpg
在討論最壞情況下的計算時間復雜度，用等號(=)還是用小於等於號(<=)是沒有本質區別的。

㈧ python分治法求二維數組局部峰值方法

python分治法求二維數組局部峰值方法
下面小編就為大家分享一篇python分治法求二維數組局部峰值方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
題目的意思大致是在一個n*m的二維數組中，找到一個局部峰值。峰值要求大於相鄰的四個元素（數組邊界以外視為負無窮），比如最後我們找到峰值A[j][i]，則有A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]。返回該峰值的坐標和值。
當然，最簡單直接的方法就是遍歷所有數組元素，判斷是否為峰值，時間復雜度為O(n^2)
再優化一點求每一行（列）的最大值，再通過二分法找最大值列的峰值（具體方法可見一維數組求峰值），這種演算法時間復雜度為O(logn)
這里討論的是一種復雜度為O(n)的演算法，演算法思路分為以下幾步：
1、找「田」字。包括外圍的四條邊和中間橫豎兩條邊（圖中綠色部分），比較其大小，找到最大值的位置。（圖中的7）

2、找到田字中最大值後，判斷它是不是局部峰值，如果是返回該坐標，如果不是，記錄找到相鄰四個點中最大值坐標。通過該坐標所在的象限縮小范圍，繼續比較下一個田字

3、當范圍縮小到3*3時必定會找到局部峰值（也可能之前就找到了）
關於為什麼我們選擇的范圍內一定存在峰值，大家可以這樣想，首先我們有一個圈，我們已知有圈內至少有一個元素大於這個圈所有的元素，那麼，是不是這個圈中一定有一個最大值？
可能說得有點繞，但是多想想應該能夠理解，也可以用數學的反證法來證明。
演算法我們理解後接下來就是代碼實現了，這里我用的語言是python（初學python，可能有些用法上不夠簡潔請見諒），先上代碼：
import numpy as np
def max_sit(*n): #返回最大元素的位置
temp = 0
sit = 0
for i in range(len(n)):
if(n[i]>temp):
temp = n[i]
sit = i
return sit
def dp(s1,s2,e1,e2):
m1 = int((e1-s1)/2)+s1 #row
m2 = int((e2-s1)/2)+s2 #col
nub = e1-s1
temp = 0
sit_row = 0
sit_col = 0
for i in range(nub):
t = max_sit(list[s1][s2+i], #第一排
list[m1][s2+i], #中間排
list[e1][s2+i], #最後排
list[s1+i][s2], #第一列
list[s1+i][m2], #中間列
list[s1+i][e2], #最後列
temp)
if(t==6):
pass
elif(t==0):
temp = list[s1][s2+i]
sit_row = s1
sit_col = s2+i
elif(t==1):
temp = list[m1][s2+i]
sit_row = m1
sit_col = s2+i
elif(t==2):
temp = list[e1][s2+i]
sit_row = e1
sit_col = s2+i
elif(t==3):
temp = list[s1+i][s2]
sit_row = s1+i
sit_row = s2
elif(t==4):
temp = list[s1+i][m2]
sit_row = s1+i
sit_col = m2
elif(t==5):
temp = list[s1+i][e2]
sit_row = s1+i
sit_col = m2
t = max_sit(list[sit_row][sit_col], #中
list[sit_row-1][sit_col], #上
list[sit_row+1][sit_col], #下
list[sit_row][sit_col-1], #左
list[sit_row][sit_col+1]) #右
if(t==0):
return [sit_row-1,sit_col-1]
elif(t==1):
sit_row-=1
elif(t==2):
sit_row+=1
elif(t==3):
sit_col-=1
elif(t==4):
sit_col+=1
if(sit_row<m1):
e1 = m1
else:
s1 = m1
if(sit_col<m2):
e2 = m2
else:
s2 = m2
return dp(s1,s2,e1,e2)
f = open("demo.txt","r")
list = f.read()
list = list.split("n") #對行進行切片
list = ["0 "*len(list)]+list+["0 "*len(list)] #加上下的圍牆
for i in range(len(list)): #對列進行切片
list[i] = list[i].split()
list[i] = ["0"]+list[i]+["0"] #加左右的圍牆
list = np.array(list).astype(np.int32)
row_n = len(list)
col_n = len(list[0])
ans_sit = dp(0,0,row_n-1,col_n-1)
print("找到峰值點位於：",ans_sit)
print("該峰值點大小為：",list[ans_sit[0]+1,ans_sit[1]+1])
f.close()

首先我的輸入寫在txt文本文件里，通過字元串轉換變為二維數組，具體轉換過程可以看我上一篇博客——python中字元串轉換為二維數組。（需要注意的是如果在windows環境中split後的列表沒有空尾巴，所以不用加list.pop()這句話）。有的變動是我在二維數組四周加了「0」的圍牆。加圍牆可以再我們判斷峰值的時候不用考慮邊界問題。

max_sit(*n)函數用於找到多個值中最大值的位置，返回其位置，python的內構的max函數只能返回最大值，所以還是需要自己寫，*n表示不定長參數，因為我需要在比較田和十（判斷峰值）都用到這個函數
def max_sit(*n): #返回最大元素的位置
temp = 0
sit = 0
for i in range(len(n)):
if(n[i]>temp):
temp = n[i]
sit = i
return sit
dp(s1,s2,e1,e2)函數中四個參數的分別可看為startx，starty，endx，endy。即我們查找范圍左上角和右下角的坐標值。
m1,m2分別是row 和col的中間值，也就是田字的中間。
def dp(s1,s2,e1,e2):
m1 = int((e1-s1)/2)+s1 #row
m2 = int((e2-s1)/2)+s2 #col

依次比較3行3列中的值找到最大值，注意這里要求二維數組為正方形，如果為矩形需要做調整
for i in range(nub):
t = max_sit(list[s1][s2+i], #第一排
list[m1][s2+i], #中間排
list[e1][s2+i], #最後排
list[s1+i][s2], #第一列
list[s1+i][m2], #中間列
list[s1+i][e2], #最後列
temp)
if(t==6):
pass
elif(t==0):
temp = list[s1][s2+i]
sit_row = s1
sit_col = s2+i
elif(t==1):
temp = list[m1][s2+i]
sit_row = m1
sit_col = s2+i
elif(t==2):
temp = list[e1][s2+i]
sit_row = e1
sit_col = s2+i
elif(t==3):
temp = list[s1+i][s2]
sit_row = s1+i
sit_row = s2
elif(t==4):
temp = list[s1+i][m2]
sit_row = s1+i
sit_row = m2
elif(t==5):
temp = list[s1+i][e2]
sit_row = s1+i
sit_row = m2

判斷田字中最大值是不是峰值，並找不出相鄰最大值
t = max_sit(list[sit_row][sit_col], #中
list[sit_row-1][sit_col], #上
list[sit_row+1][sit_col], #下
list[sit_row][sit_col-1], #左
list[sit_row][sit_col+1]) #右
if(t==0):
return [sit_row-1,sit_col-1]
elif(t==1):
sit_row-=1
elif(t==2):
sit_row+=1
elif(t==3):
sit_col-=1
elif(t==4):
sit_col+=1
縮小范圍，遞歸求解
if(sit_row<m1):
e1 = m1
else:
s1 = m1
if(sit_col<m2):
e2 = m2
else:
s2 = m2

return dp(s1,s2,e1,e2)
好了，到這里代碼基本分析完了。如果還有不清楚的地方歡迎下方留言。
除了這種演算法外，我也寫一種貪心演算法來求解這道題，只可惜最壞的情況下演算法復雜度還是O(n^2),QAQ。
大體的思路就是從中間位置起找相鄰4個點中最大的點，繼續把該點來找相鄰最大點，最後一定會找到一個峰值點，有興趣的可以看一下，上代碼：
#!/usr/bin/python3
def dp(n):
temp = (str[n],str[n-9],str[n-1],str[n+1],str[n+9]) #中 上 左 右 下
sit = temp.index(max(temp))
if(sit==0):
return str[n]
elif(sit==1):
return dp(n-9)
elif(sit==2):
return dp(n-1)
elif(sit==3):
return dp(n+1)
else:
return dp(n+9)
f = open("/home/nancy/桌面/demo.txt","r")
list = f.read()
list = list.replace(" ","").split() #轉換為列表
row = len(list)
col = len(list[0])
str="0"*(col+3)
for x in list: #加圍牆 二維變一維
str+=x+"00"
str+="0"*(col+1)
mid = int(len(str)/2)
print(str,mid)
p = dp(mid)
print (p)
f.close()
以上這篇python分治法求二維數組局部峰值方法就是小編分享給大家的全部內容了，希望能給大家一個參考