复杂度分析

复杂度分析（上）

如何分析、统计算法的执行效率和资源消耗

大 O 复杂表示法：不用具体的测试数据来测试就可以粗略地计算地模拟方法。

int cal(int n){

int sum=0;

int i=0;

for( ;i<=n;i++)

{

sum=sum+i;

}

return sum;

}

从 CPU 的角度来看，这段代码执行的操作，读数据——运算——写数据。假设每行代码执行的时间都一样，为 unit_time。

第 2，3 行代码需要一个 1unit_time

第 4，5 行代码执行了 n 遍，需要 2n 个 unit_time.

总执行时间为（2n+2)*unit_time.

结论：所有代码的执行时间 T（n)与每行代码的执行次数成正比。

公式：T（n)=O(f(n))

T(n)=O(f(n)

T(n)表示代码执行的总时间；n 表示规模大小；f(n)表示每行代码执行的次数总和。O 表示 T（n)与 f(n)成正比。

T（n)=O（2n+2)

这就是大 O 时间复杂度表示法。

大 O 时间度复杂表示法表示代码执行时间随数据增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。时间复杂度分析：

1.只关注循环执行次数最多的一段代码。

2.加法法则：总复杂度等于量级最大的那段代码的复杂度。

3.乘法法则：嵌套代码的复杂度等于嵌套内代码复杂度的乘积。

几种常见的时间复杂度分析

a.常量阶 b.指数阶 c.对数阶 d.阶乘阶 e.线性阶 f.线性对数阶 g.平方阶 h.线性阶 i。线性对数阶。

1.O（1）一般情况下，只求算法中不存在循环语句，递归语句，即便有成千上万行的代码，其时间复杂度也是 O（1）

2O(logn)、O(nlogn)

在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

3.3. O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。