数据结构基础

算法的特性

1. 输入输出

算法具有零个或者多个输入，同时，算法具有至少一个的输出。

2. 确定性

算法的每一步都具有确定的含义，无二义性。任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

3)有穷性

一个算法总是需要（输入合法的情况下）在有限的步骤结束，即每个算法需要在有穷的时间内完成。

4)可行性

一个算法是可以被执行的，即算法中的每个操作都可以通过已经实现的基本运算执行有限的次数完成。

算法设计要求

1. 正确性

正确性（Correctness）指的是该算法能够满足预先指定的功能与性能的需求，即能够得到正确答案。

2)健壮性

健壮性（Robustness）指的是当输入数据不合法时，算法也能做出相关的处理，而不是产生不可预计的效果。

3)可读性

可读性（Readability）指的是算法是可以阅读，理解和交流的。

4)耗时低，占用空间少

运行时间（Running time）与占用空间（Storage space）概念，在设计算法时，我们总是希望能够更少的使用时间和空间达成我们的目标。

基本概念和术语

1)数据

数据（Data）是信息的载体，是可以被计算机识别，存储并加工处理的描述客观事物的信息符号的总称。数据不仅仅包括了整形，浮点数等数值类型，还包括了字符甚至声音，视频，图像等非数值的类型。

2)数据元素

数据元素（Data Element）是描述数据的基本单位，也被称为记录。一个数据元素有若干个数据项组成。

如禽类，鸡鸭都属于禽类的数据元素。

3)数据项

数据项（Data Item）是描述数据的最小单位，其可以分为组合项和原子项：

a)组合项

如果数据元素可以再度分割，则每一个独立处理单元就是数据项，数据元素就是数据项的集合。

b)原子项

如果数据元素不能再度分割，则每一个独立处理的单元就是原子项。

如日期2019年4月25日就是一个组合项，其表示日期，但如果单独拿25日这个数据出来观测，这就是一个原子项，因为其不可以再分割。

4)数据对象

数据对象（Data Object）是性质相同的一类数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。

5)数据结构

数据结构（Data Structures）主要是指数据和关系的集合，数据指的是计算机中需要处理的数据，而关系指的是这些数据相关的前后逻辑，这些逻辑与计算机储存的位置无关，其主要包含以下四大逻辑结构。

四大逻辑结构（Logic Structure）

1. 集合结构

集合结构（Set Structure）中所有数据元素除了同属于一个集合外，并无其他关系。

2. 线性结构

线性结构（Linear Structure）指的是数据元素之间存在“一对一的关系”

3. 树形结构

树形结构（Tree Structure）指的是数据元素之间存在“一对多”的层次关系。

4. 图形结构

图形结构（Graphic Structure，也称：网状结构）指的是数据元素之间存在“多对多的关系”（注：此时的“多对多”中的多表示，至少有一个）

数据类型

1. 数据类型

数据类型（Data Type）是高级程序设计语言中的概念，是数据的取值范围和对数进行操作的总和。数据类型规定了程序中对象的特性。程序中的每一个变量，常量或者表达式都属于一种数据类型。

2. 抽象数据类型

抽象数据类型（Abstract Data Type，ADT）只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。

抽象数据类型的特征是实现与操作分离，从而实现封装。

复杂度

1. 时间复杂度

时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到具体的值，但我们一般并不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入时间频度（语句频度）的概念。

时间频度中，n称为问题的规模，当n不断变化时,时间频度T(n)也会不断变化。一般情况下，算法中的基本操作重复次数的是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

2)空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。

a)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

b)可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

https://www.runoob.com/wp-content/uploads/2019/03/sort.png

https://www.runoob.com/wp-content/uploads/2019/03/0B319B38-B70E-4118-B897-74EFA7E368F9.png