基本概念

数据结构

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

  • 逻辑结构（线性/树/图）

  • 物理存储结构 （数组 / 链表）

• 数据对象与一系列加载其上的操作相关两

• 完成这些操作的方法叫做算法

抽象数据类型

• 数据类型

  • 数据对象集

  • 数据集合相关联的操作集

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

  • 与存放数据的机器无关

  • 与数据存储的物理结构无关

  • 与实现操作的算法和编程语言无关

例子1

放图书

• 随便放

  1. 插入好插入

  2. 查找很难

• 按字母线性放 （一对一 ，线性结构）

  • 1. 查找变简单 ：二分查找

  • 2. 插入变难： 要将插入位置之后的书一个个移动，空出一个位置来插入书籍

• 先分类，再按字母线性放 (一对多 ，树形结构)

  • 1. 问题都解决了

  • 2. 但是分多少类合适呢？

  • 3. 如果 再将买过该书的人与书进行关联（多对多，图结构）

例子2

递归会爆内存

效率跟空间利用效率有关

例子3

第二个函数 比 第一个函数块！

• clock() ：捕捉从程序开始运行到clock()被调用时所耗费的时间，这个时间单位是clock tick，即“时钟打点”

• CLK_TCK ：机器时钟每秒所走的时钟打点数

#include <stdio.h>
#include <time.h>

clock_t start ,stop;
/* clock_t 是 clock()函数返回的变量类型 */
double duration;
/* 记录被测函数运行时间，以秒为但未*/
int main()
{

	start = clock();  /*开始计时,此时的clock*/
	MyFunction();
	stop = clock();  /*停止计时，此时的clock*/
	duration =((double)(stop - start) / CLK_TCK);

	return 0;
}

效率跟算法的巧妙程度有关

算法

算法：（Algorithm）

1. 一个有限指令集

2. 接受一些输入（有些情况下不需要输入）

3. 产生输出

4. 一定在有限步骤之后终止

5. 每一条指令必须

   1. 有充分明确的目标，不可以有歧义

   2. 计算机能处理的范围之内

   3. 描述应不依赖于任何一种计算机语言以及具体的实现手段

什么是好的算法？

• 空间复杂度S(n) -- 程序执行时占用存储单元的长度

• 时间复杂度T(n) -- 程序执行时耗费时间的长度

递归程序 -- 空间复杂度

时间复杂度 -- 只考虑程序乘法

复杂度的渐进表示法