李仙桎：个人主页
🔥 个人专栏：《数据结构与算法》
⛺️生活的理想，就是为了理想的生活!
⛺️前言：各位铁汁们好啊！！！，今天开始正式学习数据结构相关的内容，后续不断更新数据结构有关知识内容！！希望各位铁汁多多支持！这一章节主要是《数据结构》第一章 绪论 知识梳理与总结——重点掌握理解时间复杂都计算
1、掌握数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等概念。
数据(Data)
是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element)
是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理，有时也称之为结点、顶点或记录。
数据项(Data Item)
是数据元素的组成部分，是对客观事物某一方面特性的数据描述，是数据结构中讨论的最小单位，一个数据元素是由若干个数据项组成;简单数据项在处理时不能再分割;组合数据项在处理时可进一步分割。
数据对象(Data Object)
是性质相同的数据元素的集合，是数据的一个子集。如字符集合C ={A,B,C....}。
数据类型是一个值的集合和定义在此集合上面的
数据结构包含三个方面的内容（数据结构三要素），即数据的逻辑结构，数据的存储结构和对数据的运算(操作)。
三方面的关系为:
(1)数据的逻辑结构独立于计算机，是数据本身所固有的。
(2)存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机。
(3)运算是指所施加的一组操作总称。
逻辑结构（线性和非线性）
逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
逻辑结构的形式定义是一个二元组： Data-Structure=(D，S)
其中: D是数据元素的有限集，S是D上关系的有限集。
注: D上的关系S可以用序偶来表示:<x,y>(x,y属于D)。
x元素为y元素的直接前驱，y元素为x元素的直接后继。
逻辑结构类型
- 集合：同属于一个集合是数据元素之间的唯一关系。
- 线性结构：“一对一”关系，仅有一个直接前驱和一个直接后继。
- 树形结构：”一对多”关系，除根节点外仅有唯一直接前驱，所有结点都可以有0到多个直接后继。
- 图形结构：”多对多”关系，多个直接前驱和多个直接后继。
数据类型(Data Type)
数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。
1、数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有:基本类型和构造类型。
2、数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
数据结构的主要运算包括:
①建立(Create)一个数据结构（创建表）
②消除(Destroy)一个数据结构（删除表）
③从一个数据结构中删除(Delete)一个数据元素（删除表中的数据）
④把一个数据元素插入(Insert)到一个数据结构中（在表中插入一行数据）
⑤对一个数据结构进行访问(Access)（查看表）
⑥对一个数据结构(中的数据元素)进行修改(Modify)（修改表）
⑦对一个数据结构进行排序(Sort)（表排序）
⑧对一个数据结构进行查找(Search)（表查找）
抽象数据类型
抽象数据类型(Abstract Data Type，简称ADT):是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅是一组逻辑特性描述(抽象特性)，与其在计算机内的表示和实现无关(封装特性)。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组:ADT=(D，S，P)，其中:D是数据对象，S是D上的关系集，P是对D的基本操作集。
2、了解算法的定义、特性、算法的时间复杂度、算法的空间复杂度等概念，会对算法进行时间复杂度、空间复杂度分析。
算法(Algorithm)
对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法五个特性
- 有穷性:一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
- 确定性:算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
- 可行性:一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入:一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
- 输出:一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
算法的设计目标
- 正确性(Correctness):算法应满足具体问题的需求。
- 可读性(Readability):算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
- 健壮性(Robustness):算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
- 效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。
算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法
算法的效率分析
算法效率：算法效率通常是指算法运行所需的资源量，评价算法效率主要依据两个重要指标：时间复杂度和空间复杂度。
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：
事后统计：计算机执行某个算法所消耗的时间统计。存在的问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。
事前分析：求出该算法的一个时间界限函数。（常用）
3、空间复杂度
空间复杂度(Space complexity) ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作:：S(n)=O(f(n))。其中：n为问题的规模;该存储空间一般包括三个方面：
指令、常数、变量所占用的存储空间;
输入数据所占用的存储空间;
辅助存储空间。
一般地，算法的空间复杂度指的是辅助存储空间。
一维数组a[n]:空间复杂度O(n)
二维数组a[n][m]:空间复杂度O(n*m)
4、时间复杂度（重要）
时间复杂度是在计算机科学中衡量一个算法执行所需时间的量化指标。更准确来说，它不直接度量实际的时间（如秒或毫秒），而是衡量算法需要执行的操作步骤数量。计算时间复杂度通常假设每个基本操作的执行时间是固定和相同的，即使在现实中不同的操作可能需要不同的时间。算法中的基本操作的执行次数，为算法的时间复杂度。
时间复杂度表示方式O(f(n))
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O表示法通过忽略常数因子和低阶项（非主要项），专注于描述最主要的影响因素（最大的影响项），从而提供了一种比较算法效率的方法。
大O符号，记作O(f(n))，表示随着输入大小n的增加，算法的运行时间或所需空间的增长率与f(n)增长率相同或者更慢。在这里，f(n)是一个数学函数，代表随着输入规模n的变化，算法的资源消耗如何变化。
推导大O阶方法：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
有些算法的时间复杂度存在最好、平均和最坏情况（例四）：
- 最坏情况：任意输入规模的最大运行次数(上界)
- 平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界)
常见类型的时间复杂度分析（掌握）
1、for 循环——O(n)/O(log n)
void Funcation(int N){
int count = 0;
for (int i = 0; i < 2 * N ; ++ i){
++count;
}
int M = 10;
while (M--){
++count;
}
printf("%d\n", count);
}
基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N
int BinarySearch(int* a, int n, int x){ //二分查找算法
assert(a);
int begin = 0;
int end = n-1;
while (begin <= end){
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}
在每次迭代中，二分查找都会将搜索范围减半。如果数组的大小为n，则迭代如下：n,——>n/2——> n/4 ——>... ——>1。当我们达到1时，相当于进行了k次迭代，那么n/2^k = 1。解这个等式，得到n = 2^k。取对数可得k = log₂(n)。
2、多个for循环相加——O（m+n）
void Func3(int N, int M){
int count = 0;
for (int k = 0; k < M; ++ k){
++count; //执行M此
}
for (int k = 0; k < N ; ++ k){
++count; //执行N次
}
printf("%d\n", count);
}
基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)，如果有多个for循环，则多个for循环的时间复杂度相加
3、for循环嵌套——O(n*m)
void BubbleSort(int* a, int n){
assert(a); //1次
for (size_t end = n; end > 0; --end){ //n+1次
int exchange = 0; //n次
for (size_t i = 1; i < end; ++i){ //n(n-1)/2 +1次
if (a[i-1] > a[i]){ //n(n-1)/2次
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
最坏的情况发生在数组完全逆序。在这种情况下，我们需要对每一个元素做完整的n-1次比较和可能的交换，然后是n-2次，直到最后一次比较。集合中的比较次数 T 可以用以下等式来表示：
T = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
当 n 逐渐增加到非常大时，n2项占据了主导，因此我们可以将时间复杂度简化为 O(n^2)
第一个for循环的时间复杂度是O（n），第二个for循环的时间复杂度是O（n）两个嵌套后时间复杂度为O（n*n）=O(n^2)