算法复杂度的介绍

算法复杂度简介

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O( $n^{2}$ )、O( $n^{3}$ )、O( $2^{n}$ )、O(n!)、O( $n^{n}$ )

T(n)=O(f(n))

n用来表示数据规模的大小
f(n)表示代码执行次数的总和
O用来表示正比的关系
去掉所有加法项常数
只保留最高阶项
若最高阶存在，则去除最高阶前面的系数
若与对数项带阶数，直接将阶数作为系数
T()表示算法复杂度

原则：

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

我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了（由于常量，低阶和系数在O时间复杂度表示法中可省略，因为它们量级低，执行次数最多的一段代码才会是高量级）。

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

执行次数是n次的代码和执行次数是n²的代码在一起，总的复杂度是O(n²)。因为当n无限大的时候，n的时间复杂度可以省略，因为它对正比对应关系的趋势没影响。

加法法则对应成公式的形式：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

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

乘法法则是一个嵌套循环的情况：

O(n)的含义是：该算法处理数据规模为n的数据，时间复杂度为n

O( $n^{2}$ )的含义是：该算法处理数据规模为n的数据，时间复杂度为 $n^{2}$

O(n logn)的含义是：该算法处理数据规模为n的数据，时间复杂度为n logn

算法改变原始问题的处理规模

若机器1s可处理的数据规模为 $10^{8}$ ，对于O(n)复杂度的算法，1s可处理 $10^{8}$ 规模的数据

若机器1s可处理的数据规模为 $10^{8}$ ，对于O( $n^{2}$ )复杂度的算法，1s可处理 $10^{8}$ 规模的数据

（设可处理的数据规模为k，则经过此算法后数据规模变为 $k^{2}$ , $k^{2}$ = $10^{8}$ ,k= $10^{4}$ ）

算法复杂度的求法：

常量阶O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。，只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

（1）对于 i 执行n次，对于 j 执行n次，与k、m无关双层循环，故T(n)=O( $N^{2}$ )

（2）对于 i 执行n次，对于 j 执行2n次，与k、m无关双层循环，故T(n)=O(n)

（3）对于 i 执行次数设为k，则 $2^{k}= n$ ，即i的执行次数为log n，故T(n)=O(log n)

（4）对于 i 执行次数设为k，则1+2*k=n，即i的执行次数为(n-1)/2，故T(n)=O((n-1)/2)=O(n)

（5）对于 i 执行常数次，故T(n)=O(1)

（6）对于 i 执行执行常数项，j也执行常数项，故T(n)=O(1)

（7）对于 y 执行次数设为k，则 $k^{3}=n$ ，即执行次数为k= $n^{\frac{1}{3}}$ ，故T(n)=O( $n^{\frac{1}{3}}$ )

（8）对于 i 执行对于 i 执行n次，对于 j 执行n次，与k、m无关双层循环，故T(n)=O( $N^{2}$ )