关键词的选择网站提示,网站建设电销异议处理话术,wordpress媒体库修改文件名,常平镇仿做网站算法时间复杂度的计算 [整理]
时间复杂度算法
基本的计算步骤 时间复杂度的定义 一般情况下#xff0c;算法中基本操作重复执行的次数是问题规模n的某个函数#xff0c;用T(n)表示#xff0c;若有某个辅助函数f(n)#xff0c;使得当n趋近于无穷大时#xff0c;T(n)/f(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) 基本操作即算法中的每条语句以;号作为分割语句的执行次数也叫做语句的频度。在做算法分析时一般默认为考虑最坏的情况。 2. 计算出T(n)的数量级 求T(n)的数量级只要将T(n)进行如下一些操作 忽略常量、低次幂和最高次幂的系数 令f(n)T(n)的数量级。 3. 用大O来表示时间复杂度 当n趋近于无穷大时如果lim(T(n)/f(n))的值为不等于0的常数则称f(n)是T(n)的同数量级函数。记作T(n)O(f(n))。 一个示例
(1) int num1, num2;
(2) for(int i0; in; i){
(3) num1 1;
(4) for(int j1;jn; j*2){
(5) num2 num1;
(6) }
(7) } 分析
1.
语句int num1, num2;的频度为1
语句i0;的频度为1
语句in; i; num11; j1; 的频度为n
语句jn; j*2; num2num1;的频度为n*log2n
T(n) 2 4n 3n*log2n 2.
忽略掉T(n)中的常量、低次幂和最高次幂的系数
f(n) n*log2n 3.
lim(T(n)/f(n)) (24n3n*log2n) /(n*log2n) 2*(1/n)*(1/log2n) 4*(1/log2n) 3 当n趋向于无穷大1/n趋向于01/log2n趋向于0
所以极限等于3。 T(n) O(n*log2n) 简化的计算步骤 再来分析一下可以看出决定算法复杂度的是执行次数最多的语句这里是num2 num1一般也是最内循环的语句。 并且通常将求解极限是否为常量也省略掉 于是以上步骤可以简化为
1. 找到执行次数最多的语句
2. 计算语句执行次数的数量级
3. 用大O来表示结果 继续以上述算法为例进行分析
1.
执行次数最多的语句为num2 num1 2.
T(n) n*log2n
f(n) n*log2n 3.
// lim(T(n)/f(n)) 1
T(n) O(n*log2n) --------------------------------------------------------------------------------
一些补充说明
最坏时间复杂度 算法的时间复杂度不仅与语句频度有关还与问题规模及输入实例中各元素的取值有关。一般不特别说明讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。 求数量级
即求对数值(log)默认底数为10简单来说就是“一个数用标准科学计数法表示后10的指数”。例如50005x10 3 (log50003) 数量级为3。另外一个未知数的数量级为其最接近的数量级即最大可能的数量级。 求极限的技巧
要利用好1/n。当n趋于无穷大时1/n趋向于0 --------------------------------------------------------------------------------
一些规则(引自时间复杂度计算 )
1) 加法规则
T(n,m) T1(n) T2(n) O (max ( f(n),g(m) ) 2) 乘法规则
T(n,m) T1(n) * T2(m) O (f(n) * g(m)) 3) 一个特例问题规模为常量的时间复杂度
在大O表示法里面有一个特例如果T1(n) O(c) c是一个与n无关的任意常数T2(n) O ( f(n) ) 则有
T(n) T1(n) * T2(n) O ( c*f(n) ) O(f(n) ) 也就是说在大O表示法中任何非0正常数都属于同一数量级记为O(1)。 4) 一个经验规则
复杂度与时间效率的关系
c log2n n n*log2n n2 n3 2n 3n n! c是一个常量
|--------------------------|--------------------------|-------------| 较好 一般 较差
其中c是一个常量如果一个算法的复杂度为c 、 log2n 、n 、 n*log2n,那么这个算法时间效率比较高如果是 2n , 3n ,n!,那么稍微大一些的n就会令这个算法不能动了居于中间的几个则差强人意。 --------------------------------------------------------------------------------------------------
复杂情况的分析 以上都是对于单个嵌套循环的情况进行分析但实际上还可能有其他的情况下面将例举说明。 1.并列循环的复杂度分析
将各个嵌套循环的时间复杂度相加。 例如 for (i1; in; i) x; for (i1; in; i) for (j1; jn; j) x; 解
第一个for循环
T(n) n
f(n) n
时间复杂度为Ο(n) 第二个for循环
T(n) n2
f(n) n2
时间复杂度为Ο(n2) 整个算法的时间复杂度为Ο(nn2) Ο(n2)。 2.函数调用的复杂度分析
例如
public void printsum(int count){ int sum 1; for(int i 0; in;i){ sum i; } System.out.print(sum);
} 分析
记住只有可运行的语句才会增加时间复杂度因此上面方法里的内容除了循环之外其余的可运行语句的复杂度都是O(1)。
所以printsum的时间复杂度 for的O(n)O(1) 忽略常量 O(n) *这里其实可以运用公式 num n*(n1)/2对算法进行优化改为
public void printsum(int count){ int sum 1; sum count *(count1)/2; System.out.print(sum);
}
这样算法的时间复杂度将由原来的O(n)降为O(1)大大地提高了算法的性能。 3.混合情况多个方法调用与循环的复杂度分析
例如
public void suixiangMethod(int n){ printsum(n);//1.1 for(int i 0; in;i){ printsum(n); //1.2 } for(int i 0; in;i){ for(int k0; k System.out.print(i,k); //1.3 } }
suixiangMethod 方法的时间复杂度需要计算方法体的各个成员的复杂度。
也就是1.11.21.3 O(1)O(n)O(n2) ---- 忽略常数 和 非主要项 O(n2) --------------------------------------------------------------------------------------------------
更多的例子 O(1)
交换i和j的内容
tempi;
ij;
jtemp; 以上三条单个语句的频度为1该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶记作T(n)O(1)。如果算法的执行时间不随着问题规模n的增加而增长即使算法中有上千条语句其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 O(n2) sum0 /* 执行次数1 */ for(i1;in;i) for(j1;jn;j) sum /* 执行次数n2 */
解T(n) 1 n2 O(n2) for (i1;in;i) { yy1; ① for(j0;j(2*n);j) x; ② }
解 语句1的频度是n-1 语句2的频度是(n-1)*(2n1) 2n2-n-1 T(n) 2n2-n-1(n-1) 2n2-2 f(n) n2 lim(T(n)/f(n)) 2 2*(1/n2) 2 T(n) O(n2). O(n) a0; b1; ① for (i1;in;i) ② { sab; ③ ba; ④ as; ⑤ }
解 语句1的频度2, 语句2的频度n, 语句3的频度n, 语句4的频度n, 语句5的频度n, T(n) 24n f(n) n lim(T(n)/f(n)) 2*(1/n) 4 4 T(n) O(n). O(log2n) i1; ① while (in) ii*2; ②
解语句1的频度是1, 设语句2的频度是t, 则ntn; tlog2n 考虑最坏情况取最大值tlog2n, T(n) 1 log2n f(n) log2n lim(T(n)/f(n)) 1/log2n 1 1 T(n) O(log2n) O(n3) for(i0;in;i) { for(j0;ji;j) { for(k0;kj;k) xx2; } }
解当im, jk的时候,内层循环的次数为k当im时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了01...m-1(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0(1-1)*1/2...(n-1)n/2n(n1)(n-1)/2次
T(n) n(n1)(n-1)/2 (n3-n)/2
f(n) n3
所以时间复杂度为O(n3)。
