算法分析

2020-03-24 本文已影响0人努力学习的CC

时间复杂度为常数的操作：

1. 给对象赋值

2. 执行算数运算

3. 比较大小

4. 通过索引访问

5. 调用函数

6. 函数返回

我们把一个算法和一个函数f(n)联系起来，从而可以更好的帮助我们分析算法的复杂度。常见的函数类型有：

1. 常数函数 f（n）= c，上面说的

2. 对数函数 x = logbn，二分

3. 线性函数 f（n）= n，遍历

4.nlogn函数

5. 二次函数

6. 三次函数甚至更高次

7. 指数函数

常数函数 <对数函数<线性函数<nlogn函数<二次函数<三次函数<指数函数

练习：假设某个算法在输入大小为n的计算时间为 $T(n)=3*2^n$ ,在一台电脑上跑该算法用了t秒，现在用一台快64倍的计算机运行该算法，在同样的时间t内，能够处理的数据规模大小？

$旧:T(n)=3*n^2$

$新：T(n)=64*3*2^n = 3*2^{n+6}$

那么旧的电脑在t秒内处理了n个数据

$n = log_2(\frac {t}{n})$

新的电脑就可以处理：

$t = 3*2^{n+6}$

$n+6 = log_2(\frac {t}{n})$

所以可以处理n+6个文件就比旧电脑多处理了6个

vvvvvvvvvvvvvvvvv