12/25 分析算法时间复杂度的基本方法

分析算法时间复杂度的基本方法：

? ? ? ??若f（n）=+是m次多项式，则T（n）=O（）

? ? ? ? 忽略所有低次幂和最高次幂的系数，体现出增长率的含义！

1.找出语句频度最大的那条语句作为基本语句

2.计算基本语句的频度得到问题规模n的某个函数f（n）

3.取其数量级用符号“O”表示

?时间复杂度是由嵌套最深层语句的频度决定的

算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j];

T(n)=

算法时间复杂度 ：

最坏时间复杂度：指在最坏情况下，算法的时间复杂度。

平均时间复杂度：指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间，

最好时间复杂度：指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

?对于复杂的算法：

? ? ? ? 可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

? ? ? ? 1.加法规则：

? ? ? ? T（n）=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n));

? ? ? ? 2.乘法规则

? ? ? ? T（n）=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n));

算法时间效率的比较

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊！

n	f(1)	f(logn)	f(n)	f(nlogn)	f()	f()	f()	f(n!)
1	1	0	1	0	1	1	2	1
2	1	1	2	2	4	8	4	2
4	1	2	4	8	16	64	16	24
8	1	3	8	24	64	512	256	40320
16	1	4	16	64	256	4096	65536	2.0923E+13
32	1	5	32	160	1024	32768	4.295E+09	2.6313E+35

时间复杂度T(n)按数量级递增顺序为：

复杂度低? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 复杂度高

-------------------------------------------------------------------------------------------------------------------------

常数阶	对数阶	线性阶	线性对数阶	平方阶	立方阶	...	K次方阶	指数阶
O(1)	O()	O(n)	O(n)	O()	O()		O()	O()

渐进空间复杂度：

空间复杂度：算法所需存储空间的度量。

? ? ? ? 记作：S(n)=O(f(n))

其中n为问题的规模（或大小）

算法要占据的空间：

算法本身要占据的空间，输入/输出，指令，常数，变量等

算法要使用的辅助空间

算法空间复杂度分析例题

将一维数组a中的n个数逆序存放到原数组中

算法1

for(i=0;i<n/2;i++){
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}

//S(n)=O(1) 原地工作

?

?算法2

for(i=0;i<n;i++)
    b[i]=a[n-i-1];
for(i=0;i<n;i++)
    a[i]=b[i];

//S(n)=O(n)

?算法1的空间效率要高于算法2的空间效率；

?

?