算法设计与分析的题目,证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂

喵囡2022-10-04 11:39:541条回答

算法设计与分析的题目,
证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到O(n).
这是关于分治法的题

已提交,审核后显示!提交回复

共1条回复
touppp34 共回答了13个问题 | 采纳率92.3%
上面那个完全是照搬别人的嘛,问题也都不一样的.关键点在于子规模与合并这间的关系
1年前

相关推荐

算法设计与分析 已知某个算法的时间复杂度T(n)=O(f(n)),f(n)是什么函数?T(n)和f(n)是什么关系?
zhengxm_husq1年前1
康明斯发动机 共回答了23个问题 | 采纳率91.3%
时间复杂度
算法分析
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率.算法分析的目的在于选择合适算法和改进算法.一个算法的评价主要从时间复杂度和空间复杂度来考虑.
1、时间复杂度
(1)时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n).
(2)时间复杂度
在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化.但有时我们想知道它变化时呈现什么规律.为此,我们引入时间复杂度概念.
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数.记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度.
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2).
按数量级递增排列,常见的时间复杂度有:
常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),...,
k次方阶O(nk),指数阶O(2n).随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低.
算法设计与分析的题目求解考虑下面的算法:输入:n个元素的组数A输出:按递增顺序排序的数组Avoid sort (int
算法设计与分析的题目求解
考虑下面的算法:
输入:n个元素的组数A
输出:按递增顺序排序的数组A
void sort (int A[ ],int n)
{
int i,j,temp;
for(i=0;i
情深深,雨蒙蒙1年前1
yvonnefang 共回答了19个问题 | 采纳率89.5%
冒泡~
所有元素都是排好的,一次赋值都木有

所有元素都是递减的,每次都赋值,(1+n-1)*(n-1)/2次
算法设计与分析在任何一个2k*2k的棋盘覆盖问题中,用到的L型骨牌个数为().A.(4k-1)/3 B.(4k-1)/2
算法设计与分析
在任何一个2k*2k的棋盘覆盖问题中,用到的L型骨牌个数为().
A.(4k-1)/3 B.(4k-1)/2 C.(2k-1)/3 D.(2k-1)/2
EricQQ1年前1
紫浪璧衫 共回答了26个问题 | 采纳率92.3%
应该是(4(k^2)-1)/3
算法设计与分析 证明n!=Θ(n^n)
TD小子1年前1
滴雨星 共回答了24个问题 | 采纳率100%
n!/(n^n)=(1/n)(2/n)……(n/n)
求帮我下算法设计与分析!1令A[1..n]是一个由n个数所组成的数组。序列A[1], A[2], … , A[n]被称为
求帮我下算法设计与分析!
1
令A[1..n]是一个由n个数所组成的数组。序列A[1], A[2], … , A[n]被称为是单模的(unimodal),当且仅当存在顶点序号1≤p≤n,使得数组的元素从A[1]、A[2]开始到A[p]单调增加,而从A[p]、A[p+1]开始到A[n]则单调下降。
问题:对于一个给定的单模序列A[1], A[2], … , A[n],请找出其顶点序号p。设计一个求解此问题的算法并分析其最坏时间复杂性。
2
设有一个算法Median能在O(n)的时间内计算一个数组的中位值(即将数组的元素按大小顺序排列正好位于中间的值)。给定一个有n个元素的数组,能否以Median算法为基础设计一个算法,对任意的整数1≤i≤n,该算法在O(n)的时间内求出数组中第i大小的元素。如果能,请给出一个这样的算法并分析其最坏时间复杂性。
likeavirgin1年前1
dengbin010 共回答了17个问题 | 采纳率88.2%
说下思路吧 都是用分治做的 取中点 x_i 看左右 x_{i-1} x_{i+1} 根据这三个点关系判断顶点在哪侧 之后递归处理那边用类似快排的思路 但用pivot做partition之后只用递归的处理一边 具体题主可以看一下《算法导论》 的顺序统计量那一章 有具体的算法和分析
算法设计与分析问题:3阶魔方阵.
算法设计与分析问题:3阶魔方阵.
要求在一个N xN的矩阵中填入1到n2(n的二次方)的数字(n为奇数),如图所示3阶魔方阵
(1)证明:n阶魔方阵中每一行、每一列、每条对角线的累加和一定等于n(n2+1)/2;
(2)设计蛮力算法生成n阶魔方阵.还有其他更好的算法吗?
ii拍板1年前1
dqgonggan 共回答了23个问题 | 采纳率87%
如果我们将1,2,……n2按某种规则依次填入到方阵中,得到的恰好是奇次魔方阵,这个规则可以描述如下:
(1)首先将1填在方阵第一行的中间,即(1,(n+1)/2)的位置;
(2)下一个数填在上一个数的主对角线的上方,若上一个数的位置是(i,j),下一个数应填在(i1,j1),其中i1=i-1、j1=j-1.
(3)若应填写的位置下标出界,则出界的值用n 来替代;即若i-1=0,则取i1=n;若j-1=0,则取j1=n.
(4)若应填的位置虽然没有出界,但是已经填有数据的话,则应填在上一个数的下面(行加1,列不变),即取i1=i+1,j1=j.
这样循环填数,直到把n*n个数全部填入方阵中,最后得到的是一个n阶魔方阵.
main( )
{int i,j,i1,j1,x,n,t,a[100][100];
print(“input an odd number:”);
input(n);
if (n mod 2=0) {print(“input error!”); return;}
for( i=1;i
算法设计与分析:求解递推关系:f(n)=4f(n-1)-4f(n-2),当n≥2;f(n)=6,f(1)=8
iuc71年前3
izam2003 共回答了15个问题 | 采纳率100%
λ^2-4λ+4=0
解得,λ1=λ2=2;
f(n)= (c1+nc2)2^n
然后代2值解出来c1,c2,就行了,
不会是理工学院的吧~!一同挂科好了
算法设计与分析习题谁会做给定数组A=(98,31,22,44,37,9)试用分治法求其第二小元素(要求使用SELECT算
算法设计与分析习题谁会做
给定数组A=(98,31,22,44,37,9)
试用分治法求其第二小元素
(要求使用SELECT算法)
hongaikai1年前1
sysshang 共回答了18个问题 | 采纳率94.4%
这个是利用分治思想来解
考点是快排
可以用二分法对原数组进行排序
快排(QuickSort)是一种基于分治思想的二分排序法.对于一段序列,我们先
选出一个划分元素,然后用线性的时间复杂度将大于和小于划分元素的元素
移动到划分元素的两边,再由划分元素处将序列拆分为两部分,分别进一步
处理.显然这里划分元素的选择决定了拆分序列的平均程度.
因为算法是二分的,每段序列的处理是线性的,易知时间复杂度为O(nlgn).
可是假设每一次选择的划分元素都是序列里最大或最小的,那么拆分的时间
复杂度也会变成线性的,所以快排在最坏情况下的时间复杂度为O(N^2).
如何实现这个算法?(算法设计与分析 书中的题)
如何实现这个算法?(算法设计与分析 书中的题)
设R={r1,r2,...,rn}(r后面是下标)是要进行排列的n个元素,Ri=R-{ri}.集合X中元素的全排列记为perm(X).(ri)perm(X)表示在全排列perm(x)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下:
当n=1时,perm(R)=(r),其中r是集合中唯一的元素;
当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)构成.
由此递归定义,可设计产生perm(R)的递归算法如下:
public static int perm(Object[]list,int k,int m)
{//产生list[k:m]的所有排列
if(k==m)
{//只剩一个元素
for(int i=0;i
kouneng1年前1
牵着企鹅去飞 共回答了15个问题 | 采纳率100%
不太懂算法,不过swap在程序里通常指数组或集合中两个元素的交换
就像这样:
public static void swap(Object[] list, int m, int n) {
Object temp = list[m];
list[m] = list[n];
lsit[n] = temp;
}
算法设计与分析求解设有n个活动的集合E={1,2,…,n},每个活动i(i∈E)都有一个要求使用公共资
算法设计与分析求解
设有n个活动的集合E={1,2,…,n},每个活动i(i∈E)都有一个要求使用公共资源的起始时间si和一个结束时间fi,且si
窗外的月光1年前1
taty_2008 共回答了32个问题 | 采纳率90.6%
(1)贪心算法吧
先排序 si从小到大,fi也是从小到大.
总是选择si 最先满足>fi的活动 而且这个fi保证是当前最小的.
要假设以某个活动为开始时间 然后进行比较
复杂度O(n的二次方)
我一直觉得动态规划也可以 但是自己水平有限.