数据结构自学笔记 2018-09-22

第一章

第一节：计算

1.1计算

计算机无非是工具和手段，计算才是我们本质的研究目的和目标。

从绳索计算机和尺规计算机的两个例子中看到：计算机无疑只是工具，而就计算 ：就是运用相应的工具，可以重复，机械的（完成问题解决）的过程。

1.2算法

所谓算法，即在特定的计算模型下，旨在解决特定问题的指令序列

具有以下几个特征;

1.输入

2.输出

3.正确性 的确可以解决指定问题

4.确定性 应当可以被描述为一个由基本操作组成的序列

5.可行性 每个操作是可以实现的 （不要犯大象塞冰箱的错误）

6.有穷性 对于任何输入，有穷次基本操作，都可以得到输出

1.3好算法

1.首先，它是正确的

2.可读的：结构化，注释，准确命名

3.最重要的：效率 ----- 速度尽可能的快，占用储存空间尽可能少

第二节 计算模型

2.1 性能测度

算法有有效性和高效性，前提是数据结构和算法的有机结合，统称DSA，而效率，则是区分不同DSA“好坏”，“优劣”的标准。而要定量的分析，则要用到下面的算法分析。

2.2 算法分析

1.前提：正确性

2.核心：成本：时间成本和空间成本，但要分辨两个DSA的成本大小，你必须保证两个计算成本一致，

通常，两个问题的规模一致时，我们的就可以视为两个问题的计算成本一致。

2.3最坏情况

我们在计算一个DSA的成本T(n)时，考虑的是最坏情况下的T(n)的值。