一、几个基本的定义

1、数据（data）：描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切可以输入计算机并能被处理的都是数据。
例如除了表示人的姓名、身高、体重等的字符、数字是数据，人的照片、指纹、三维模型、语音指令等也都是数据。
2、数据项（data item）：数据项具有原子性，是不可分割的最小数据单位。
如描述学生相关信息的姓名、性别、学号等都是数据项；
三维坐标中的每一维坐标值也是数据项。数据项具有原子性，是不可分割的最小单位。
3、数据元素（data element）：数据的基本单位，是数据集合的个体，通常由若干个数据项组成，在计算机程序中通常作为一个整体来进行处理。
例如一条描述一位学生的完整信息的数据记录就是一个数据元素；空间中一点的三维坐标也可以是一个数据元素。
4、数据对象（data object）：性质相同的数据元素的集合，是数据的子集。
例如一个学校的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象。

比较

5、数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合。
组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。
表示一组数据元素及其相互关系的数据结构有两种不同的表现形式：
一种是数据结构的逻辑层面，即数据的逻辑结构；
一种是存在于计算机世界的物理层面，即数据的存储结构。

数据结构

二、数据结构的类型

1、数据的逻辑结构：

数据的逻辑结构指数据元素之间的逻辑关系（和实现无关）。
分类1：线性结构和非线性结构
线性结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
线性表就是一个典型的线性结构，它有四个基本特征：
1．集合中必存在唯一的一个"第一个元素"；
2．集合中必存在唯一的一个"最后的元素"；
3．除最后元素之外，其它数据元素均有唯一的"直接后继"；
4．除第一元素之外，其它数据元素均有唯一的"直接前驱"。

线性结构示意图

非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。
常见的非线性结构有：树(二叉树等)，图(网等)。

非线性结构案例

分类2：集合结构 线性结构 树状结构 网络结构
集合结构：就是数学中所学习的集合。集合中的元素有三个特征：
1).确定性（集合中的元素必须是确定的）
2).唯一性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1）
3).无序性（集合中的元素没有先后之分），如集合{3,4,5}和{3,5,4}算作同一个集合
该结构的数据元素间的关系是“属于同一个集合”，别无其它关系。
线性结构：数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
树状结构：除了一个数据元素（元素 01）以外每个数据元素有且仅有一个直接前驱元素，但是可以有多个直接后续元素。
特点是数据元素之间是 1 对 多的联系
网络结构：每个数据元素可以有多个直接前驱元素，也可以有多个直接后续元素。特点是数据元素之间是多对 多 的联系

各种结构示意图（按顺序）

2、数据的存储结构

数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示，是数据的逻辑结构在计算机中的表示。
常见的存储结构有顺序存储，链式存储，索引存储，以及散列存储。

顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如C/C++）的数组来描述的。
（数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素，在存储器中的相对位置来反映）

顺序存储结构

优点：
1.节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
2.采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
缺点：
1.插入和删除操作需要移动元素，效率较低。
2.必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。

链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素。
每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
逻辑上相邻的节点物理上不必相邻。
缺点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、查找结点时链式存储要比顺序存储慢。
优点：
1、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
2.有元素才会分配结点空间，不会有闲置的结点。

索引存储结构：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储结构：根据结点的关键字直接计算出该结点的存储地址，例如HashSet HashMap的底层实现

数据的结构

三、算法（algorithm ）

指令的集合，是为解决特定问题而规定的一系列操作。

一个算法通常来说具有以下五个特性：
输入：一个算法应以待解决的问题的信息作为输入。
输出：输入对应指令集处理后得到的信息。
可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。
确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。
简单的说，算法就是计算机解题的过程。

评价算法优劣的依据：复杂度（时间复杂度和空间复杂度）
算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度
时间复杂度是指执行算法所需要的计算工作量；
空间复杂度是指执行这个算法所需要的内存空间。

四、算法的时间复杂度（Time Complexity)

1、时间频度

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度，表示为T（n），n表示问题的规模。

2、时间复杂度

时间复杂度就是时间频度去掉低阶项和首项常数。T(n)=O(f(n))
注意：时间频度与时间复杂度是不同的，时间频度不同但时间复杂度可能相同。

3、最坏时间复杂度和平均时间复杂度

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
为了进一步说明算法的时间复杂度，我们定义 Ο、Ω、Θ符号：
Ο(欧米可荣)符号给出了算法时间复杂度的上界（最坏情况 <=），比如T（n） =O（n2）
Ω(欧米伽)符号给出了时间复杂度的下界（最好情况 >=），比如T（n） =Ω（n2）
而Θ(西塔)给出了算法时间复杂度的精确阶（最好和最坏是同一个阶 =），比如T（n） =Θ（n2）

4、时间复杂度的计算

⑴ 找出算法中的基本语句；
　　 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
　　 ⑵ 计算基本语句的执行次数的数量级；
　　 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，
可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
　　 ⑶ 用大Ο记号表示算法的时间性能。
　　 将基本语句执行次数的数量级放入大Ο记号中。

5、常用的时间复杂度级别

常数阶O(1) 
对数阶O(log2n)
线性阶O(n)
线性对数阶O(n*log2n)
平方阶O(n2) 
立方阶O(n3)
...
k次方阶O(nk)
指数阶O(2n)
阶乘阶O(n!)

上面各种时间复杂度级别，执行效率越来越低。

五、空间复杂度（Space Complexity)

算法的存储量包括:
1．程序本身所占空间
2．输入数据所占空间；
3．辅助变量所占空间
输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：S(n) = O(g(n))

空间复杂度分析1：

int fun(int n){   
    int i，j，k，s; 
        s=0;
        for (i=0;i<=n;i++)           
            for (j=0;j<=i;j++)      
                    for (k=0;k<=j;k++)     
                        s++; 
        return(s);
}

由于算法中临时变量的个数与问题规模n无关，所以空间复杂度均为S(n)=O(1)。

空间复杂度分析2：

void fun(int a[]，int n，int k) 
   //数组a共有n个元素
 {  int i;
    if (k==n-1)
       for (i=0;i<n;i++)　　
        printf(“%d\n”，a[i]);  //执行n次
    else
    {  for (i=k;i<n;i++)
        a[i]=a[i]+i*i;  　　//执行n-k次
       fun(a，n，k+1);
    }
 } 

此属于递归算法，每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。
注意：
1.空间复杂度相比时间复杂度分析要少
2.对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；
若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。