博客

这一章主要讲解时间和空间复杂度。

时间复杂度T(n)表示一个程序解决所需时间

Omega<=T<=O

空间复杂度S(n)表示一个程序所需内存空间

数据结构中最重要的概念是数据抽象

数据抽象不依赖于元素类型，不依赖于存储方式，比依赖与具体实现 方法（如语言）

算法：算法是一个有限指令集，它接受一些输入，产生输出并在一定步后结束

递归解决方法的优点是思维简单，反复调用，缺点是空间复杂度远大于循环实现

算法复杂度中：

N!>X^N>N^3>N^2>N LOGN>N>LOGN

log一般是使用分治法实现的优化

当出现n^2是尽量降为NlogN,当n^3以上是基本放弃算法

求f(x)=a0+a1x+a2x^2…

最好是使用秦九韶算法即内部拆解，以减少空间复杂度。

另外可使用C标准库 clock_t 类型定义开始结束时间

clock_t start,stop;
double duration;
start=clock();
f1();
stop=clock();
duration=(double)(stop-start)/CLK_TCK;//clock()表示当前时间，CLK_TCK表示每秒打点数