从哪个网站设置宽带主机,国际外贸平台排名,网站建设工具的实验心得,wordpress标签云文章目录一、时间复杂度二、空间复杂度三、相关题目一、时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)#xff0c;它是该算法问题规模n的函数#xff0c;时间复杂度主要分析T(n)的数量级。算法中基本运算#xff08;最深… 文章目录一、时间复杂度二、空间复杂度三、相关题目一、时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)它是该算法问题规模n的函数时间复杂度主要分析T(n)的数量级。算法中基本运算最深层循环内的语句的频度与T(n)同数量级因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此算法的时间复杂度记为T(n)O(f(n))。
式中O的含义是T(n)的数量级其严格的数学定义是若T(n)和f(n)是定义在正整数集合上的两个函数则存在正常数C和n0使得当nn0时都满足0T(n)Cf(n)。
算法的时间复杂度不仅依赖于问题的规模n也取决于待输入数据的性质。例如在数组A[0…n-1]中查找给定值k的算法大致如下
int in-1;
while(i0(A[i]!k))i--;
return i; 该算法中语句i--;基本运算的频度不仅与问题规模n有关还与输入实例中A的各元素的取值以及k的取值有关 ①若A中没有与k相等的元素则语句3的频度f(n)n。 ①若A中最后一个元素为k则语句3的频度f(n)0。
最坏时间复杂度是指在最坏情况下算法的时间复杂度。平均时间复杂度是指所有可能输入实例在等概率出现的情况下算法的期望运行时间。最好时间复杂度是指在最好情况下算法的时间复杂度。一般总是考虑在最坏情况下的时间复杂度以保证算法的运行时间不会比它更长。
在分析一个程序的时间复杂性时有以下两条规则 ①加法规则
T(n)T1(n)T2(n)O(f(n))O(g(n))O(max(f(n),g(n)))②乘法规则
T(n)T1(n)*T2(n)O(f(n))*O(g(n))O(f(n)*g(n))常见的渐近时间复杂度为
O(1)O(logn)O(n)O(nlogn)O(n*n)O(n*n*n)O(2的n方)O(n!)O(n的n方)二、空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间它是问题规模n的函数。记为S(n)O(g(n))。
一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身和算法无关则只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需的辅助空间为常量即O(1)。 三、相关题目
1 以下算法的时间复杂度为O(log2n)
void fun(int n){int i1;while (in)ii*2;
}解析找到基本运算ii*2设执行次数为t则2的t次方n即tlog2n因此时间复杂度T(n)O(log2n)。
2 有以下算法其时间复杂度为O(n的根号3方)
void fun(int n){int i0;while (i*i*in)i;
}解析基本运算为i设执行次数为t有tttn即t的3次方n则tn的根号3次方。
3 程序段如下
for(int i n-1; i 1; i--)for (int j 1; j i; j) if(A[j]A[j1])A[j]与A[j1]对换;其中n为正整数则最后一行语句的频度在最坏情况下是O(n*n) 解析
4 【2011统考真题】设n是描述问题规模的非负整数下面的程序片段的时间复杂度是O(log2n)
x2;
while(xn/2)x2*x;解析基本运算为x2*x每执行一次乘以2设执行次数为t则有2的t1次方n/2所以tlog2(n/2)-1log2n-2则T(n)O(log2n)。
5 【2012统考真题】求整数n的阶乘的算法如下其时间复杂度是O(n)
int fact(int n){if(n1) return 1;return n* fact(n-1);
}解析该递归相当于返回O(n)次。
6 【2013统考真题】已知两个长度分别为m和n的升序链表若将它们合并为长度为mn的一个降序链表则最坏情况下的时间复杂度是O(max(m,n)) 解析两个升序链表合并两两比较表中元素每比较一次确定一个元素的链接位置取较小元素。当一个链表比较结束后将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较因为2max(m,n)mn所以时间复杂度为O(max(m,n))。
7 【2014统考真题】下列程序段的时间复杂度是nlong2n
count0;
for(k1;kn;k*2)for(j1;jn;j)count;解析内层循环条件jn与外层循环的变量无关各自独立每执行一次j自增1每次内层循环都执行n次。外层循环条件kn增量定义为k*2可知循环次数t满足k2的t次方n即tlog2n。内层循环的时间复杂度为O(n)外层为O(log2n)。对于嵌套循环根据乘法法则可知T(n)O(n)*O(log2n)O(nlog2n)。
