分治法的算法复杂度

㈠ 多项式乘法分治算法的时间复杂度怎样计算

长度为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分治法求二维数组局部峰值方法就是小编分享给大家的全部内容了，希望能给大家一个参考