1数据结构的分类，算法效率的度量

一，数据结构的定义和分类

数据结构：数据之间的关系即数据的逻辑结构，因为要存储到计算机里，所以视为将这个数据的逻辑结构映射到存储器里。即数据因为自身的和其他的数据的关系而在计算机内存储的方式。我们就归类了一些类型。

二，算法的定义和效率度量

算法：数据之间要运算，不同的数据结构也有更适合自己的算法，题目中也不会说告诉你要怎么存储使用数据，需要自己辨别，并在多个算法中根据算法效率的度量（两个），选择最优的算法。

算法效率的度量：

1.时间复杂度T(n)=O(f(n))

1>怎么算：

①只看语句重复最多次的那个语句称为基本语句，比如如果是多层嵌套则最深层的嵌套即基本语句

②多层嵌套可以借助数学公式求和

例

③找出执行次数k与n的关系，表示为k=g(n)，即O(k)=O(g(n)）为所求

例

④运用加法法则和乘法法则：可以分成几个可以估算的部分

⑤忽略低次幂项（即忽略不是最大执行频率的语句）和最高次幂系数（即常数不要）

例

2>时间复杂度的分类：选平均和最坏居多，默认最坏，以保证算法的运行时间不比它长

例：用顺序查找在n个元素数组中找key，最好：1次即1；最坏：n次即n；平均：O(n/2)=O(n)

3>算法时间效率的比较（用图像记）

O(log2n)可以直接写成O(logn)，这种对数的其实下角标不重要

2.空间复杂度S(n)=O(f(n))

空间复杂度是算法所需存储空间的度量，由以下两个部分组成

算法本身需要占据的空间：变量，常数，指令，输入输出

算法要使用的辅助空间

例：这里t和b[i]都是辅助空间，相当于临时用的