有关时间复杂度
算法时间复杂度（转）
2011-03-0623:28:18|分类：“IT 牛杂”|字号订阅
1. 算法分析的评价体系
评价算法的三条主要标准是：
(1)算法实现所消耗的时间
(2)算法实现所消耗的存储空间，其中主要考虑辅助存储空间
(3)算法应易于理解、易于编码、易于调试。
2. 算法的时间复杂性
2.1和算法执行相关的因素
(1)问题中数据存储的数据结构
(2)算法采用的数学模型
(3)算法设计策略
(4)问题的规模
(5)实现算法的程序设计语言
(6)编译算法产生的机器代码的质量
(7)计算机执行指令的速度
2.2算法时间效率的衡量方法
(1)事后分析法
先将算法用程序设计语言实现，然后度量程序的运行时间，这种方法成为事后分析法。你能想到它的缺点???
(2)事前分析估算法
一个算法的运行工作量的大小，只依赖于问题的规模(通常用整数量n 表示) ，或者说算法的时间效率是问题规模的函数。
假如随着问题规模n 的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=O(f(n)),T(n)简称时间复杂度，
O 是数量级的符号。
2.3时间复杂度估算
算法的执行时间=
(1)例子1
Java 代码
for (j=1; j <=n; j++)
for(k=1; k <=n; k++)
x++;
for (j=1; j <=n; j++)for(k=1; k <=n; k++)x++;$[原操作的执行次数*原操作的执行时间]，其中, $表示累加. 语句的频度指的是该语句重复执行的次数。
分析:算法段中语句"x++","k<=n","x++"的频度是n*n,语句
"j=1","k=1"的频度是1，语句"j<=n","j++"的频度是n 。
因此，算法运行的时间是3*n*n+2*n+2
(2)例子2
Java 代码
for (j=1; j <=n; j++)
for(k=1; k <=n; k++)
for(i=1; i <=n; i++)
s++;
for (j=1; j <=n; j++)
s++;
该算法的时间复杂度为近似n*n*n.
(3)O
在算法的复杂度分析中经常使用一个记号O ，读作大O ，它是数量级Order 的第一个字母。当一个算法的运行时间为n*n+n+1时，
由于n*n+n+1和n*n的数量级相等(该表达式当n 足够大时约等于n*n),称它为这个算法的渐进时间复杂度，简称算法的时间复杂度，
记作：T(n)=O(n*n).
(4)几种数量级
O(1)
O(logn)
O(n)
O(n的c 次方)
O(c的n 次方)
O(n!)常数级对数级线性级多项式级指数级阶乘级for(k=1; k <=n; k++)for(i=1; i <=n; i++)
(5)问题时间复杂度的上界和下界
(6)算法时间复杂度的最好情况和最坏情况
2.4算法的空间复杂性
(1)输入数据所占空间
(2)程序本身所占空间
(3)辅助存储空间
有关时间复杂度
算法时间复杂度（转）
2011-03-0623:28:18|分类：“IT 牛杂”|字号订阅
1. 算法分析的评价体系
评价算法的三条主要标准是：
(1)算法实现所消耗的时间
(2)算法实现所消耗的存储空间，其中主要考虑辅助存储空间
(3)算法应易于理解、易于编码、易于调试。
2. 算法的时间复杂性
2.1和算法执行相关的因素
(1)问题中数据存储的数据结构
(2)算法采用的数学模型
(3)算法设计策略
(4)问题的规模
(5)实现算法的程序设计语言
(6)编译算法产生的机器代码的质量
(7)计算机执行指令的速度
2.2算法时间效率的衡量方法
(1)事后分析法
先将算法用程序设计语言实现，然后度量程序的运行时间，这种方法成为事后分析法。你能想到它的缺点???
(2)事前分析估算法
一个算法的运行工作量的大小，只依赖于问题的规模(通常用整数量n 表示) ，或者说算法的时间效率是问题规模的函数。
假如随着问题规模n 的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=O(f(n)),T(n)简称时间复杂度，
O 是数量级的符号。
2.3时间复杂度估算
算法的执行时间=
(1)例子1
Java 代码
for (j=1; j <=n; j++)
for(k=1; k <=n; k++)
x++;
for (j=1; j <=n; j++)for(k=1; k <=n; k++)x++;$[原操作的执行次数*原操作的执行时间]，其中, $表示累加. 语句的频度指的是该语句重复执行的次数。
分析:算法段中语句"x++","k<=n","x++"的频度是n*n,语句
"j=1","k=1"的频度是1，语句"j<=n","j++"的频度是n 。
因此，算法运行的时间是3*n*n+2*n+2
(2)例子2
Java 代码
for (j=1; j <=n; j++)
for(k=1; k <=n; k++)
for(i=1; i <=n; i++)
s++;
for (j=1; j <=n; j++)
s++;
该算法的时间复杂度为近似n*n*n.
(3)O
在算法的复杂度分析中经常使用一个记号O ，读作大O ，它是数量级Order 的第一个字母。当一个算法的运行时间为n*n+n+1时，
由于n*n+n+1和n*n的数量级相等(该表达式当n 足够大时约等于n*n),称它为这个算法的渐进时间复杂度，简称算法的时间复杂度，
记作：T(n)=O(n*n).
(4)几种数量级
O(1)
O(logn)
O(n)
O(n的c 次方)
O(c的n 次方)
O(n!)常数级对数级线性级多项式级指数级阶乘级for(k=1; k <=n; k++)for(i=1; i <=n; i++)
(5)问题时间复杂度的上界和下界
(6)算法时间复杂度的最好情况和最坏情况
2.4算法的空间复杂性
(1)输入数据所占空间
(2)程序本身所占空间
(3)辅助存储空间