数据结构导论【数据结构系列（一）】

1. 数据结构的基本概念

数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入计算机中并被计算机程序识别和处理符号的集合。

---

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成，数据项是构成数据元素不可分割的最小单位。

---

数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

---

数据类型：数据类型是一个值的集合，和定义在此集合上的一组操作的总称。

---

①原子类型。（其值不可再分的数据类型）
 
②结构类型。（其值可以再分为若干成分的数据类型。）
 
③抽象该数据类型。
抽象数据类型是对数据类型的一种抽象描述，它定义了一组操作和对应的语义规则，而不关注具体实现细节。（比如，在python中使用面向对象编程的思想，定义一个类，这个“类”即为抽象数据类型。）

---

数据结构：数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。

---

数据结构的三要素：

① 数据的逻辑结构
 
② 数据的存储结构
 
③ 数据的运算

---

2.数据的逻辑结构

逻辑结构，是对数据之间关系的描述。主要有以下四大类。
 

①集合结构：数据元素之间除了同属于一个集合，再无任何联系。
 
②线性结构：结构中的数据元素之间存在一对一的关系。其中除了第一个元素，每个元素都有唯一前驱。除了最后一个元素，每个元素都有唯一后继。
 
③树形结构：结构中数据元素之间存在一对多的关系。
 
④图形结构：结构中的数据元素之间存在多对多的关系。

以上四种中，除了线性结构外，其余三种都是非线性结构。

---

3.数据的存储结构

存储结构 是指数据在计算机内存或外部存储器中的实际存储方式（又称映像）。（也称为物理结构）
 
常见的存储结构包括：

顺序存储结构
 
链式存储结构
 
索引存储结构
 
散列存储结构

这里记住名字就行了，理解不了不用强行理解。后边学到每个对应的部分的时候，再对各种结构分别理解即可。

---

4. 算法

程序 = 数据结构+算法

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

算法的特性：

算法的目标：

---

5.算法的时间复杂度

算法的时间复杂度是衡量算法执行所需时间的指标。它描述了算法执行时间与输入规模的关系。
 
它表示随着输入规模增加，算法执行所需的时间的增长速度。时间复杂度通常用大O符号（O）表示。
 
常见的时间复杂度包括：

常数时间复杂度（O(1)）：无论输入规模大小，算法执行时间都保持不变。
 
对数时间复杂度（O(log n)）：算法的执行时间与输入规模的对数成正比。
 
线性时间复杂度（O(n)）：算法的执行时间与输入规模成线性关系。
 
线性对数时间复杂度（O(n log n)）：算法的执行时间与输入规模的对数乘以线性关系。
 
平方时间复杂度（O(n^2)）：算法的执行时间与输入规模的平方成正比。
 
指数时间复杂度（O(2^n)）：算法的执行时间随着输入规模的指数增长。
 

选择高效的算法和数据结构可以减少算法的时间复杂度，从而提高算法的执行效率。

---

5.1常数阶 O(1)

以以下代码为例，通过求和公式直接计算1+2+...+n的值。无论n为多少，代码的执行次数是恒定的，一直都是3次。

# include <stdio.h>

int main(){
    int sum=0,n=100; //执行1次
    sum = (1+n)*n/2; //执行1次
    printf("sum=%d\n",sum); //执行1次
    return 0;
}
1
2
3
4
5
6
7
8

此种情况，我们称之为具有常数阶$O(1)$的时间复杂度。

---

5.2 线性阶 $O(n)$

以以下代码为例，通过逐步累加来计算1+2+...+n的值。
 
需要注意的是，我们只关注循环体内的操作次数，即sum += i这一行代码的执行次数，以及其他额外的操作次数（比如int i,sum=0,n=100，printf 语句），而不会计算或考虑循环的初始化和判断条件部分的执行次数。
 
代码的执行次数与n是有线性关系的，共计执行1+n+1次，即 $(n+2)$ 次。

# include <stdio.h>

int main(){
    int i,sum=0,n=100; //执行1次
    for(i=1;i<=n;i++){
        sum += i;  //执行n次
    }
    printf("sum=%d\n",sum); // 执行1次
    return 0;
}
1
2
3
4
5
6
7
8
9
10

所以该算法的时间复杂度为$O(n)$。

__

5.3 对数阶 $O(logn)$

以以下代码为例，代码共执行了m+2次，其中m满足$m>=lo{g}_{2}n$，这里不必考虑的非常精确，将m其视为$lo{g}_{2}n$即可。执行次数即可以视为$lo{g}_{2}n+2$。

# include <stdio.h>

int main(){
    int count=1,n=100; //执行1次
    while(count<n)  //执行m+1次，m满足2**m>=n，则 m>=log2 n。（虽然写出来了，但是不考虑该执行次数）
    {
        count*=2; //执行m次
    }
    printf("count=%d\n",count); //执行1次
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

所以该算法的时间复杂度为$O(logn)$。
（$O(logn)$默认表示底数为2。）

---

5.4 平方阶 $O(n^2)$

以下边的循环嵌套为例。

# include <stdio.h>

int main(){
    int i,j,n=5; //执行1次
    for(i=0;i<n;i++) //执行n次（不考虑）
    {
        for(j=0;j<n;j++) //执行n次（不考虑）
        {
            printf("%d\n",j); //执行n*n次
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

因为内层循环共执行了$n^2$次，所以该算法的算法复杂度为$O(n^2)$。

---

5.5时间复杂度的大小比较

常用的时间复杂度所耗费的时间从小到大依次是：

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2n)<O(n!)<O(n^n)$
 
当n为一个具体的数字时，以10为例，则有：
 
$O(1)<O(log10)<O(10)<O(10log10)<O(100)<O(1000)<O(1024)<O(10^{10})$

---

5.6 最好、最坏 与 平均情况

还以线性阶的代码为例。假设n是一个变量，而不再是一个定值，这里以规定n是大于等于1的，且小于等于100。
 

# include <stdio.h>

int main(){
    int i,sum=0,n=100; //执行1次
    for(i=1;i<=n;i++){ //执行n+1次（不考虑）
        sum += i;  //执行n次
    }
    printf("sum=%d\n",sum); // 执行1次
    return 0;
}
1
2
3
4
5
6
7
8
9
10

---

当n为1时是最好情况，循环部分的代码只执行了一次。故程序一共执行了3次。则算法的时间复杂度为O(1)。
 
当n为100时，则为最坏情况。时间复杂度为O(n)。
 
除此之外，还有平均情况。时间复杂度为O(n)。

也许你会产生疑惑，但是解释如下：
 
在时间复杂度的表示中，常数因子通常不会包含在大O表示法中。这是因为时间复杂度是用来描述算法性能随着输入规模增加而变化的趋势，而不是具体的执行时间。
 
所以，在最坏情况下，即当n=100时，我们 仍然使用O(n) 来表示时间复杂度，而不是O(100)。这是因为O(n)更好地反映了算法的增长率和对输入规模的敏感程度。无论n的值是多少，该算法的运行时间都呈线性增长。

---

6. 算法的空间复杂度

算法的空间复杂度可以理解为，在问题的数据规模发生变化时，算法执行消耗的空间（内存空间）如何变化。
 
需要注意的是，空间复杂度描述的不是算法执行消耗的空间。这一点雨时间复杂度类似，时间复杂度也不是消耗的时间，而是时间如何变化。
 
计算空间复杂度，一般计算的是“额外空间”，数据自身的空间一般则不考虑。

---