数据结构入门第一课（浙大mooc笔记）

数据结构入门第一课

数据结构入门第一课

测试程序运行时间

clock(): 捕捉从程序开始到clock()被调用时候所耗费的时间。这个时间单位是clock_tick，即为时间打点。

常数CLK_TCK:机器时钟每秒所走的时钟打点数。

一个常见用法范例：

#include <time.h>
clock_t starttime,endtime;
double time;
starttime=clock();
//my function...
endtime=clock();
time=(double）（endtime-starttime)/CLK_TCK;
/*in some computers may be 
/*time=(double)(endtime - starttime)/ CLOCKS_PER_SEC;

什么是数据结构？

数据对象在计算机中的组织方式：

逻辑结构

物理存储结构

数据对象必然与一系列加在其上的操作相关联；

实现这些操作所用的方法叫算法；

抽象数据类型（abstract data type）

数据类型：

数据对象集

数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

只描述是什么，不关心怎么做到。

例1.4 矩阵的定义见书 or ppt

什么是算法

一个有限指令集；

接受一些输入（可以没有），必须有输出；

一定在有限步骤之内终止；

每一条指令必须：有充分明确的目标，不可以有歧义；在计算机能够处理的范围内；描述不依赖于任何一种计算机语言以及具体的实现手段。

什么是好的算法

空间复杂度S(n)

执行时占用存储单元的长度。

时间复杂度T(n)

执行时耗费时间的长度。

两种重要复杂度

最坏情况复杂度T_worst(n)

平均复杂度T_ave(n)

T_ave(n)<=T_worst(n)

复杂度的渐进表示法

看到复杂度为n^2时候，下意识要想降低到nlogn;