一、基本概念和术语

数据
数据元素：是数据的基本单位。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象：是性质相同的数据元素的集合。

》数据结构

1.逻辑结构

【线性结构】

- 线性表
    - 一般线性表
    - 特殊线性表
        - 栈与队列
        - 字符串
    - 线性表的推广
        - 数组
        - 广义表

【非线性结构】

- 树结构
    - 树
    - 二叉树
- 图结构
    - 有向图
    - 无向图
- 集合结构

2.存储结构（物理结构）

数据元素及其关系在计算机存储器中的存储方式。

【顺序存储结构】

通常是借助元素在储存器中的相对位置来表示数据元素之间的逻辑关系，通常借助数组类型来描述。

【链式存储结构】

通常借助于指针类型来描述。

二、算法和算法分析

数据结构中，用时间复杂度来衡量程序运行时间的多少；用空间复杂度来衡量程序运行所需内存空间的大小。运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。

1.时间复杂度

如何预估一个算法所编程序的运行时间呢？很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。

算法的时间复杂度取决于“问题的规模”和“待处理数据的初态”。

以一段简单的 C 语言程序为例，预估出此段程序的运行时间：

for(int i = 0 ; i < n ; i++)     // 从 0 到 n，执行 n+1 次
{
    a++;                         // 从 0 到 n-1，执行 n 次
}

数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。

再举一个例子：

for(int i = 0 ; i < n ; i++)           // n+1
{ 
    for(int j = 0 ; j < m ; j++)       // n*(m+1)
    {
        num++;                         // n*m
    }
}

计算此段程序的频度为：(n+1)+n*(m+1)+n*m，简化后得 2*n*m+2*n+1。

数据结构推出了大 O 记法（注意是大写的字母 O ）来表示算法（程序）的运行时间，格式为： O(频度)

其中，这里的频度为最简之后所得的频度。
比如，以无限大的思想来简化 2n²+2n+1。
当 n 无限大时：

首先，常数 1 是可以忽略不计的；

其次，对于指数级的 2n² 来说，是否在其基础上加 2n，并无关紧要；

甚至于，对于是否给 n² 乘 2，也可以忽略。

因此，最终频度 2n²+2n+1 可以简化为 n² 。

常用的几种时间复杂度，以及它们之间的大小关系：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

算法的时间复杂度分析举例请见课本P13页

2.空间复杂度

和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。

每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

程序代码本身所占用的存储空间；
程序中如果需要输入输出数据，也会占用一定的存储空间；
程序在运行过程中，可能还需要临时申请更多的存储空间。（影响最大）

常见的几种空间复杂度：

如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1) ；
反之，如果有关，则需要进一步判断它们之间的关系：
如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n²) 表示；
如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n³) 表示；
等等。

在多数场景中，一般情况下，鉴于运算空间比较充足，一个好的算法往往更注重的是“时间复杂度”的比较，而空间复杂度只要在一个合理的范围内就可以。

【时间复杂度的分析举例】

基本方法：找到所有语句中语句频度最大的那条语句，作为基本语句，计算其语句频度得到关于问题规模n的函数f(n)，取其数量级并用 O(频度) 表示即可。

1.常量阶示例

{x++; s=0; }

两条语句的频度均为1，算法的时间复杂度为T(n)=O(1)

for(i=0; i<10000; i++){x++; s=0; }

循环体内两条基本语句的频度均为常数，算法的时间复杂度为T(n)=O(1)，称为常量阶。

如果问题规模n是个确定的值，那么算法的执行时间就不随n值变化了，是一个与n无关的常数。即便这个常数再大，算法的时间复杂度均为T(n)=O(1)。

2.线性阶示例

for(i=0; i<n; i++){x++; s=0; }

循环体内两条基本语句的频度均为f(n)= n，算法的时间复杂度为T(n)=O(n)，称为线性阶。

这里的问题规模n是一个不确定的数，n越大，执行时间也会随n值变化而越长。

3.平方阶示例

x=0; y=0;
for(k=1; k<=n; k++)
    x++;
for (i=1; i<n; i++)             
    for (j=i; j<=n ; j++)       
        y++;                  //语句频度最大

对于循环语句，只需考虑循环体中语句的执行次数。以上程序中最后一句的语句频度均为 f(n)=n² ，算法的时间复杂度为：T(n)=O(n²)，称为平方阶。

多数情况下，对于若干个循环语句，算法的时间复杂度由最深层循环内的基本语句的频度决定。

4.立方阶示例

x=1;
for (i=1; i<=n; i++)             
    for (j=i; j<=n ; j++)       
        for(k=1; k<=n; k++)
            x++;              //语句频度最大

该算法的时间复杂度为：T(n)=O(n³)，称为立方阶。

5.对数阶示例

for(i=1; i<n; i=i*2){
    x++; s=0;                //设语句频度为f(n)
}

设语句频度为f(n)，也就是最大执行次数是f(n)，当 i=2^f(n)≤n 时该循环语句才会执行，由此可得语句频度：f(n)≤log₂ n，所以该算法的时间复杂度为：T(n)=O(log₂ n)，称为对数阶。

i=1;
while(i<=n)
    i=i*3;

语句频度：f(n)≤log₃ n

6.根号阶（瞎编的名）

x=n;      // n>1
y=0;
while(x>=(y+1)*(y+1))
    y++;                    //设语句频度为f(n)

设语句频度为f(n)，也就是最大执行次数是f(n)，当 x>=(y+1)^2f(n) 时该循环语句才会执行，由此可得语句频度：f(n)≤√n ，所以该算法的时间复杂度为：T(n)=O(√n)

参考内容:

[1] http://data.biancheng.net/view/272.html
[2] https://blog.csdn.net/weixin_45704695/article/details/104611481
[3] https://blog.csdn.net/weixin_44589374/article/details/107851422