如图，该算法复杂度递归函数的空间复杂度f(n)的渐进性分析哪些是正确的？

来源：蜘蛛抓取(WebSpider) 时间：2023-03-25 06:03 标签： 递归函数的空间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，基座T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进算法时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
一般用大写O()来表示算法的时间复杂度写法，通常叫做大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
O(1)：常数阶
O(n)：线性阶
O(n2)：平方阶
大O推导法：
用常数1取代运行时间中的所有加法常数 在修改后的运行函数中，只保留最高阶项 如果最高阶项存在且不是1，则去除与这个项相乘的常数
常数阶：
int sum = 0 ; n = 100;
/*执行一次*/
sum = (1+n)*n/2;
/*执行一次*/
printf("%d",sum);
/*执行一次*/
复制代码
这个算法的运行次数f(n) = 3,根据推导大O阶的方法，第一步是将3改为1，在保留最高阶项是，它没有最高阶项，因此这个算法的时间复杂度为O(1);
另外，
int sum = 0 ; n = 100;
/*执行一次*/
sum = (1+n)*n/2;
/*执行第1次*/
sum = (1+n)*n/2;
/*执行第2次*/
sum = (1+n)*n/2;
/*执行第3次*/
sum = (1+n)*n/2;
/*执行第4次*/
sum = (1+n)*n/2;
/*执行第5次*/
sum = (1+n)*n/2;
/*执行第6次*/
sum = (1+n)*n/2;
/*执行第7次*/
sum = (1+n)*n/2;
/*执行第8次*/
sum = (1+n)*n/2;
/*执行第9次*/
sum = (1+n)*n/2;
/*执行第10次*/
printf("%d",sum);
/*执行一次*/
复制代码
上面的两段代码中，其实无论n有多少个，本质是是3次和12次的执行差异。这种与问题的大小无关，执行时间恒定的算法，成为具有O(1)的时间复杂度，又叫做常数阶。 注意：不管这个常数是多少，3或12，都不能写成O(3)、O(12)，而都要写成O(1)
此外，对于分支结构而言，无论真假执行的次数都是恒定不变的，不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中），其时间复杂度也是O(1)。
线性阶：
线性阶的循环结构会复杂一些，要确定某个算法的阶次，需要确定特定语句或某个语句集运行的次数。因此要分析算法的复杂度，关键是要分析循环结构的运行情况。
int i;
for(i = 0 ; i < n ; i++){
/*时间复杂度为O(1)的程序*/
}
复制代码
对数阶：
int count = 1;
while(count < n){
count = count * 2;
/*时间复杂度为O(1)的程序*/
}
复制代码
因为每次count*2后，距离结束循环更近了。也就是说有多少个2 相乘后大于n，退出循环。 数学公式：2x = n --> x = log2n 因此这个循环的时间复杂度为O(logn) 平方阶：
int i;
for(i = 0 ; i < n ; i++){
for(j = 0 ; j < n ; j++){
/*时间复杂度为O(1)的程序*/
}
}
复制代码
上面的程序中，对于对于内层循环，它的时间复杂度为O(n)，但是它是包含在外层循环中，再循环n次，因此这段代码的时间复杂度为O(n2)。
int i;
for(i = 0 ; i < n ; i++){
for(j = 0 ; j < m ; j++){
/*时间复杂度为O(1)的程序*/
}
}
复制代码
但是，如果内层循环改成了m次，时间复杂度就为O(n*m) 再来看一段程序：
int i;
for(i = 0 ; i < n ; i++){
for(j = i ; j < n ; j++){
/*时间复杂度为O(1)的程序*/
}
}
复制代码
注意：上面的内层循环j = i ;而不是0
因为i = 0时，内层循环执行了n次，当i=1时，执行了n-1次……当i=n-1时，执行了1次，所以总的执行次数为：
n+(n-1)+(n-1)+...+1 = n(n+1)/2 = n2/2 + n/2
根据大O推导方法，保留最高阶项，n2/2 ，然后去掉这个项相乘的常数，1/2
因此，这段代码的时间复杂度为O(n2)
下面，分析调用函数时的时间复杂度计算方法：
首先，看一段代码：
int i,j;
void function(int count){
print(count);
}
for(i = 0 ; i < n ; i++){
function (i)
}
复制代码
函数的时间复杂度是O(1)，因此整体的时间复杂度为O(n)。
假如function是这样的：
void function(int count){ int j; for(j = count ; j < n ;j++){ /时间复杂度为O(1)的程序/ } }
和第一个的不同之处在于把嵌套内循环放到了函数中，因此最终的时间复杂度为O(n2)
再来看一个比价复杂的语句:
n++;
/*执行次数为1*/
function(n);
/*执行次数为n*/
int i,j;
for(i = 0 ; i < n ; i++){
/*执行次数为nXn*/
function(i);
}
for(i = 0 ; i < n ; i++){
/*执行次数为n(n+1)/2*/
for(j = i ; j < n ; j++){
/*时间复杂度为O(1)的程序*/
}
}
复制代码
它的执行次数f(n) = 1 + n + n2 + n(n+1)/2 + 3/2n2+3/2 n+1, 根据推导大O阶的方法，最终它的时间复杂度为：O(n2) 常见的时间复杂度：
结论： 时间复杂度所耗费的时间是： O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) <O(2n) < O(n!) <O(nn)

笔试部分
一．简答题(40分)
1.算法的基本概念、性质及其与程序的联系与区别
算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
算法性质：输入---有零个或者多个外部量作为算法的输入；
输出---算法产生至少一个量最为输出；
确定性：组成算法的每条指令是清晰的、无歧义的；
有限性：算法中指令的执行次数有限和执行的时间有限。
程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。
2.大O表示法的含义和渐进时间复杂度（要会计算复杂度）
大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
3.分治法的基本思想是什么
分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
4.回溯算法的基本思想及其一般模式（子集树+排列树）
基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
搜索子集树的一般模式：
void search(int m)
{
if(m>n) //递归结束条件
output(); //相应的处理(输出结果)
else
{
a[m]=0; //设置状态：0表示不要该物品
search(m+1); //递归搜索：继续确定下一个物品
a[m]=1; //设置状态：1表示要该物品
search(m+1); //递归搜索：继续确定下一个物品 }
}
搜索排列树的一般模式：
void search(int m)
{
上一页下一页

我要回帖

更多关于 递归函数的空间复杂度 的文章

 

随机推荐