目录前言数据的相关概念一数据Data二数据元素Data Element三数据结构 (Data Structure)四数据元素的表示方法算法与算法分析一算法的特性与要求二算法的效率度量三算法的不同量级性能比较四空间复杂度前言相信通过前面的序言大家对于数据结构的重要性与必要性也依旧具有初步的了解。那么在本章我们将探讨数据结构常用的概念包括数据数据元素数据对象数据结构数据类型抽象数据结构算法的概念算法的效率度量以及算法的存储空间度量等数据结构中的必备通识。这些通识虽然仅是《数据结构》中最最基础的概念同样也是对不同数据结构不同算法进行设计分析的必要根本。那么下面就让我们打开数据结构的大门迈出第一步。数据的相关概念一数据Data数据(data)数据是对一种事物的符号的表示。通俗来讲数据就是通过多种符号来表示现实世界的事物。比如当你在数学中求解二元一次方程组时会对若干个多项式进行标号用序号来代表某个多项式。这就是对一种事物的符号表示。在广义定义中数据是信息的载体数据是构成信息的基本单位。二数据元素Data Element数据元素data element数据元素是数据的基本单位在程序中通常当作一个整体。数据元素由若干个数据项组成是数据项的容器。数据项data item数据项是数据不可分割的最小单位是构成数据元素的基本单元。如函氏去吃过桥米线那么对于这一碗过桥米线来说过桥米线这道菜即为数据元素过桥米线里的米线汤汁肥牛等即为组成这个数据元素的数据项。用数学逻辑来说数据项既是数据元素的真子集也是数据元素的非空子集。数据对象data object数据对象是具有相同性质的数据元素的集合。还是拿函氏去吃过桥米线为例如果函氏想要吃到这碗过桥米线需要在商家的小程序上进行下单排队。那么对于这个下单排队程序中所有下单过桥米线的人称为是数据对象那么分配到每一个个体上函氏就是这个数据对象中的数据元素。这里先小小剧透一下实现这个程序用到了一个名字叫“队列”的数据结构此结构见后续章节这是一种先进先出FIFO的结构与大家去食堂排队买饭联想起来是不是觉得“队列”这个数据结构能够生动的描述出这种类似的日常生活的场景。这就是队列的最基础最容易联想到的应用场景。三数据结构 (Data Structure)数据结构data structure数据结构是场景中相互之间存在一种或多种特定联系的数据元素的集合。对于这个数据结构目前学界还没有一个确切严谨的定义。为了让大家能够比较清晰的理解什么叫数据结构我们依旧拿函氏去吃过桥米线为例。已知函氏是此场景中的一个数据元素。那么对于排队的若干顾客来说他们之间呈现出一种一个对应一个的逻辑关系这个关系即为线性结构。每一个人通过这个“一对一”的关系组合而成的集合就是数据结构。由于数据元素之间具有不同的联系数据元素间通常具有以下四种结构集合与数学上的集合定义类似集合中的数据元素除了从属于同一集合外别无其他关系。集合这种结构的具体实现为后面要讲到的并查集并查集是一种经典的集合数据结构的实现。线性结构数据元素间存在一对一的关系像一条链子 。如上面所讲的排队取号的例子就是经典的线性结构。树状结构结构中数据元素存在一对多的关系。树状结构就像树枝一样一根树枝可以有多个分叉每个分叉还会有多个更小的分叉。树状结构最攘夷联想到的就是计算机内的文件存储。计算机的文件存储就是树状结构。根目录下会有多个文件夹或文件夹每个文件夹又会有多个文件或文件夹。图状结构或网状结构结构中的元素存在多对多的关系。将多对多的数据元素的关系表示出来像是一张网。比如函氏要梳理一本小说的人物关系时所梳理的任务关系便会呈现出网状的结构以上为四种基数据结构。四数据元素的表示方法逻辑结构在结构中的数据元素之间的逻辑关系称为逻辑结构。即不看数据元素在计算机内是如何存储的只看数据元素之间的逻辑关系。简单来说数据元素间的逻辑结构是看数据与数据间是怎么“排队”怎么“关联”的。所以逻辑结构与二中的数据结构中的数据元素之间的关系相同。数据的逻辑结构分为线性结构、集合、树状结构、图状或网状结构。存储结构即数据在计算机内是如何存储的。数据的存储结构分为两大类顺序存储 链式存储顺序存储数据与数据在物理空间上看是连续的。需要在计算机内申请一块连续的内存空间用来存储数据。具体表现形式为数组。链式存储数据与数据在物理空间上看是不连续的。链式存储常需要在计算机内申请一小块内存空间用来存储数据的data与指向下一块内存空间的指针。存储数据的区域我们称之为数据域存储指针的区域我们称之为指针域。这样申请的每一小块内存空间我们称之为一个结点。数据运算对数据进行的种种运算操作。最常用的有增删改查等。同一逻辑结构可以对应多种存储结构由此我们可以总结出数据结构的三要素存储结构、逻辑结构、数据运算。下面我们来探讨链式存储域顺序存储的优缺点顺序存储优点可以对数据进行随机存取申请连续空间空间利用率高代码实现简单缺点插入删除操作效率低下大小固定无法动态扩容想要增加容量只能重新申请内存空间。但是在高级语言c/java/python中支持动态扩容链式存储优点插入删除快只需要移动指针即可存储容量可动态改变直接申请扩容不要求空间连续可利用碎片空间缺点无法随机访问必须从头遍历元素代码实现较顺序存储复杂存储密度低算法与算法分析一算法的特性与要求算法Algorithm算法是对特定问题求解步骤的描述。算法共有5种特性有穷性一个算法必须总是经过又穷步之后结束对于每一步都在合理的可接受的时间范围内完成。确定性算法种的每一条指令都必须由明确的含义不会让人产生歧义可行性理论存在的现实可行的不知不能是模糊抽象的操作不能无限依赖精度和时间。输入一个算法可以有零个或多个输入。输出一个算法可以有一个或多个输出。算法设计的要求确定性算法要能满足当下问题的需求。可读性算法的变量定义等要通俗易懂。健壮性算法要再输入非法数据时不输出脏数据。效率与低存储量一个好的算法我们要让它的执行效率与所占用空间尽可能的降低。二算法的效率度量一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数f(n)那么算法的时间度量记作T(n)O(f(n))它表示随问题规模n的增大算法时间的增长率与f(n)的增长率相同叫做算法的时间复杂度。那么再实际分析算法的过程中我们分析一个算法的时间复杂度只需要求一个算法内重复执行语句的频度即语句重复执行的次数即可。对于嵌套循环我们需要对各循环层次的代码执行频次进行相乘。在分析算法的时间复杂度时我们可以采用渐进分析的方法重点关注随着输入规模n增大时算法执行时间的主要增长趋势。根据渐进分析的原则可以省略对于算法的时间复杂度影响不大的低阶项和常数系数。例如若一个算法的时间复杂度为O(3n² 2n 100)我们可以简化为O(n²)因为当n趋向于无穷大时n²项的增长速度远快于n和常数项。对于O(5n³ 1000n)这样的复杂度可以简化为O(n³)因为n³的增长速度远超过线性项。特殊情况如O(log n 1)可以简化为O(log n)因为常数1在n很大时相对log n可以忽略不计。这种简化方法基于以下考虑在理论分析中我们更关注算法执行时间的增长趋势实际应用中当输入规模足够大时高阶项将主导算法的运行时间简化后的复杂度表示更便于比较不同算法的性能需要注意的是这种简化方法适用于理论分析但在实际工程实现中对于小规模输入被忽略的低阶项可能仍然会产生显著影响。举一个例子有如下c/c代码void printHanShi(int n){ if(n0){ for(int i0;in;i){ cout函氏要吃i碗麻辣烫endl; } } }在上面代码种如果n10则for循环种的cout函氏要吃i碗麻辣烫endl;会执行10次。如果n100则又会执行100次。由此可见上述代码的时间复杂度为O(n)。又如下面代码void bubbleSort(vectorint arr) { int n arr.size(); // 外层循环控制排序轮数 for (int i 0; i n - 1; i) { // 内层循环比较相邻元素并交换 for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { // 交换元素 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }此为c实现的冒泡排序算法。首先输入一个数组int n arr.size();获取数组长度仅执行一次时间复杂度为O(1);接下来进入外层循环由for循环可知循环变量i从0~n-2总共执行了n-1轮。又因为对于循环条件判断自增操作的时间复杂度均为O(1)所以外层循环的时间复杂度为O(n)。接下来看内层循环第 i 轮内层循环执行次数为 n-i-1 次。总比较次数将括号打开为省略对时间复杂度影响不大的常数项后冒泡排序算法的时间复杂度为O()。通过上述例子相信大家依旧初步了解算法的时间复杂度的概念与求法。在这里函氏交给大家在408考研时间复杂度选择题的“邪修”法。这个“邪修”办法我们姑且称之为“用特殊值求解时间复杂度”。方法如下我们首先设n为64。(n太大的话计算麻烦n太小的话计算的精度不够)然后我们模拟代码运行列出代码执行的频度。再将n64带入选项查看选项的计算结果哪个与代码的执行频度最接近即可。举一个2011年408统考真题的例子。有如下代码片段x2; while(xn/2) x2*x;A.O() B.O(n) C.O() D.o()求代码片段的时间复杂度 根据我们的“邪修”办法我们先设n64然后我们模拟代码的运行当n64时代码循环了4次。接着将n64带入选项选项A为6选项B为64选项C为64×6选项D为64的平方。显而易见该题的正确答案是A。三算法的不同量级性能比较不管是在应试考试还是在实际应用中算法的性能比较都是我们必会的一项基础技能。那么对于不同量级的时间复杂度他们的时间复杂度性状大小为O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ)记忆口诀常对幂指阶O(1)常数时间操作时间与输入规模无关。O(log n)对数时间常见于二分查找等分治算法。O(n)线性时间操作时间与输入规模成正比。O(n log n)线性对数时间常见于高效排序算法如快速排序、归并排序。O(n²)平方时间常见于简单排序算法如冒泡排序。O(n³)立方时间常见于矩阵乘法等。O(2ⁿ)指数时间常见于暴力搜索算法。实际应用选择小规模数据O(n²)算法可能足够因实现简单。大规模数据需选择O(n log n)或更低复杂度的算法。实时系统优先考虑时间复杂度稳定的算法避免最坏情况下的性能波动。优化策略空间换时间使用哈希表O(1)访问替代线性搜索O(n)。分治策略将问题分解为更小的子问题降低复杂度。剪枝与缓存避免重复计算如动态规划中的备忘录技术。上述优化策略等到后续章节具体情况具体分析。四空间复杂度空间复杂度空间复杂度类似于时间复杂度的定义算法的空间复杂度指算法所需存储空间的度量。记作S(n)O(f(n))在实际分析中我们主要考虑算法使用的额外空间不包括输入数据本身占用的空间。常见的空间复杂度包括O(1)常数空间如交换两个变量的算法O(n)线性空间如需要创建与输入规模相同的数组O(n²)平方空间如某些动态规划算法需要二维数组存储中间结果O(1)的空间复杂度也称之为原地算法。示例递归实现的斐波那契数列的空间复杂度为O(n)因为递归调用栈的深度与n成正比而迭代实现的空间复杂度为O(1)只需要存储前两个值。需要注意的是空间复杂度的分析与时间复杂度类似都是关注增长趋势而非具体数值通常会忽略常数项和低阶项。以上便是本章《数据结构与算法》通识篇的全部内容。欢迎评论指正。作为本系列的第一篇技术类博文有不足之处多多海涵。下一章顺序表的定义及基础操作
《数据结构与算法》-- 数据结构的通识
目录前言数据的相关概念一数据Data二数据元素Data Element三数据结构 (Data Structure)四数据元素的表示方法算法与算法分析一算法的特性与要求二算法的效率度量三算法的不同量级性能比较四空间复杂度前言相信通过前面的序言大家对于数据结构的重要性与必要性也依旧具有初步的了解。那么在本章我们将探讨数据结构常用的概念包括数据数据元素数据对象数据结构数据类型抽象数据结构算法的概念算法的效率度量以及算法的存储空间度量等数据结构中的必备通识。这些通识虽然仅是《数据结构》中最最基础的概念同样也是对不同数据结构不同算法进行设计分析的必要根本。那么下面就让我们打开数据结构的大门迈出第一步。数据的相关概念一数据Data数据(data)数据是对一种事物的符号的表示。通俗来讲数据就是通过多种符号来表示现实世界的事物。比如当你在数学中求解二元一次方程组时会对若干个多项式进行标号用序号来代表某个多项式。这就是对一种事物的符号表示。在广义定义中数据是信息的载体数据是构成信息的基本单位。二数据元素Data Element数据元素data element数据元素是数据的基本单位在程序中通常当作一个整体。数据元素由若干个数据项组成是数据项的容器。数据项data item数据项是数据不可分割的最小单位是构成数据元素的基本单元。如函氏去吃过桥米线那么对于这一碗过桥米线来说过桥米线这道菜即为数据元素过桥米线里的米线汤汁肥牛等即为组成这个数据元素的数据项。用数学逻辑来说数据项既是数据元素的真子集也是数据元素的非空子集。数据对象data object数据对象是具有相同性质的数据元素的集合。还是拿函氏去吃过桥米线为例如果函氏想要吃到这碗过桥米线需要在商家的小程序上进行下单排队。那么对于这个下单排队程序中所有下单过桥米线的人称为是数据对象那么分配到每一个个体上函氏就是这个数据对象中的数据元素。这里先小小剧透一下实现这个程序用到了一个名字叫“队列”的数据结构此结构见后续章节这是一种先进先出FIFO的结构与大家去食堂排队买饭联想起来是不是觉得“队列”这个数据结构能够生动的描述出这种类似的日常生活的场景。这就是队列的最基础最容易联想到的应用场景。三数据结构 (Data Structure)数据结构data structure数据结构是场景中相互之间存在一种或多种特定联系的数据元素的集合。对于这个数据结构目前学界还没有一个确切严谨的定义。为了让大家能够比较清晰的理解什么叫数据结构我们依旧拿函氏去吃过桥米线为例。已知函氏是此场景中的一个数据元素。那么对于排队的若干顾客来说他们之间呈现出一种一个对应一个的逻辑关系这个关系即为线性结构。每一个人通过这个“一对一”的关系组合而成的集合就是数据结构。由于数据元素之间具有不同的联系数据元素间通常具有以下四种结构集合与数学上的集合定义类似集合中的数据元素除了从属于同一集合外别无其他关系。集合这种结构的具体实现为后面要讲到的并查集并查集是一种经典的集合数据结构的实现。线性结构数据元素间存在一对一的关系像一条链子 。如上面所讲的排队取号的例子就是经典的线性结构。树状结构结构中数据元素存在一对多的关系。树状结构就像树枝一样一根树枝可以有多个分叉每个分叉还会有多个更小的分叉。树状结构最攘夷联想到的就是计算机内的文件存储。计算机的文件存储就是树状结构。根目录下会有多个文件夹或文件夹每个文件夹又会有多个文件或文件夹。图状结构或网状结构结构中的元素存在多对多的关系。将多对多的数据元素的关系表示出来像是一张网。比如函氏要梳理一本小说的人物关系时所梳理的任务关系便会呈现出网状的结构以上为四种基数据结构。四数据元素的表示方法逻辑结构在结构中的数据元素之间的逻辑关系称为逻辑结构。即不看数据元素在计算机内是如何存储的只看数据元素之间的逻辑关系。简单来说数据元素间的逻辑结构是看数据与数据间是怎么“排队”怎么“关联”的。所以逻辑结构与二中的数据结构中的数据元素之间的关系相同。数据的逻辑结构分为线性结构、集合、树状结构、图状或网状结构。存储结构即数据在计算机内是如何存储的。数据的存储结构分为两大类顺序存储 链式存储顺序存储数据与数据在物理空间上看是连续的。需要在计算机内申请一块连续的内存空间用来存储数据。具体表现形式为数组。链式存储数据与数据在物理空间上看是不连续的。链式存储常需要在计算机内申请一小块内存空间用来存储数据的data与指向下一块内存空间的指针。存储数据的区域我们称之为数据域存储指针的区域我们称之为指针域。这样申请的每一小块内存空间我们称之为一个结点。数据运算对数据进行的种种运算操作。最常用的有增删改查等。同一逻辑结构可以对应多种存储结构由此我们可以总结出数据结构的三要素存储结构、逻辑结构、数据运算。下面我们来探讨链式存储域顺序存储的优缺点顺序存储优点可以对数据进行随机存取申请连续空间空间利用率高代码实现简单缺点插入删除操作效率低下大小固定无法动态扩容想要增加容量只能重新申请内存空间。但是在高级语言c/java/python中支持动态扩容链式存储优点插入删除快只需要移动指针即可存储容量可动态改变直接申请扩容不要求空间连续可利用碎片空间缺点无法随机访问必须从头遍历元素代码实现较顺序存储复杂存储密度低算法与算法分析一算法的特性与要求算法Algorithm算法是对特定问题求解步骤的描述。算法共有5种特性有穷性一个算法必须总是经过又穷步之后结束对于每一步都在合理的可接受的时间范围内完成。确定性算法种的每一条指令都必须由明确的含义不会让人产生歧义可行性理论存在的现实可行的不知不能是模糊抽象的操作不能无限依赖精度和时间。输入一个算法可以有零个或多个输入。输出一个算法可以有一个或多个输出。算法设计的要求确定性算法要能满足当下问题的需求。可读性算法的变量定义等要通俗易懂。健壮性算法要再输入非法数据时不输出脏数据。效率与低存储量一个好的算法我们要让它的执行效率与所占用空间尽可能的降低。二算法的效率度量一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数f(n)那么算法的时间度量记作T(n)O(f(n))它表示随问题规模n的增大算法时间的增长率与f(n)的增长率相同叫做算法的时间复杂度。那么再实际分析算法的过程中我们分析一个算法的时间复杂度只需要求一个算法内重复执行语句的频度即语句重复执行的次数即可。对于嵌套循环我们需要对各循环层次的代码执行频次进行相乘。在分析算法的时间复杂度时我们可以采用渐进分析的方法重点关注随着输入规模n增大时算法执行时间的主要增长趋势。根据渐进分析的原则可以省略对于算法的时间复杂度影响不大的低阶项和常数系数。例如若一个算法的时间复杂度为O(3n² 2n 100)我们可以简化为O(n²)因为当n趋向于无穷大时n²项的增长速度远快于n和常数项。对于O(5n³ 1000n)这样的复杂度可以简化为O(n³)因为n³的增长速度远超过线性项。特殊情况如O(log n 1)可以简化为O(log n)因为常数1在n很大时相对log n可以忽略不计。这种简化方法基于以下考虑在理论分析中我们更关注算法执行时间的增长趋势实际应用中当输入规模足够大时高阶项将主导算法的运行时间简化后的复杂度表示更便于比较不同算法的性能需要注意的是这种简化方法适用于理论分析但在实际工程实现中对于小规模输入被忽略的低阶项可能仍然会产生显著影响。举一个例子有如下c/c代码void printHanShi(int n){ if(n0){ for(int i0;in;i){ cout函氏要吃i碗麻辣烫endl; } } }在上面代码种如果n10则for循环种的cout函氏要吃i碗麻辣烫endl;会执行10次。如果n100则又会执行100次。由此可见上述代码的时间复杂度为O(n)。又如下面代码void bubbleSort(vectorint arr) { int n arr.size(); // 外层循环控制排序轮数 for (int i 0; i n - 1; i) { // 内层循环比较相邻元素并交换 for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { // 交换元素 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }此为c实现的冒泡排序算法。首先输入一个数组int n arr.size();获取数组长度仅执行一次时间复杂度为O(1);接下来进入外层循环由for循环可知循环变量i从0~n-2总共执行了n-1轮。又因为对于循环条件判断自增操作的时间复杂度均为O(1)所以外层循环的时间复杂度为O(n)。接下来看内层循环第 i 轮内层循环执行次数为 n-i-1 次。总比较次数将括号打开为省略对时间复杂度影响不大的常数项后冒泡排序算法的时间复杂度为O()。通过上述例子相信大家依旧初步了解算法的时间复杂度的概念与求法。在这里函氏交给大家在408考研时间复杂度选择题的“邪修”法。这个“邪修”办法我们姑且称之为“用特殊值求解时间复杂度”。方法如下我们首先设n为64。(n太大的话计算麻烦n太小的话计算的精度不够)然后我们模拟代码运行列出代码执行的频度。再将n64带入选项查看选项的计算结果哪个与代码的执行频度最接近即可。举一个2011年408统考真题的例子。有如下代码片段x2; while(xn/2) x2*x;A.O() B.O(n) C.O() D.o()求代码片段的时间复杂度 根据我们的“邪修”办法我们先设n64然后我们模拟代码的运行当n64时代码循环了4次。接着将n64带入选项选项A为6选项B为64选项C为64×6选项D为64的平方。显而易见该题的正确答案是A。三算法的不同量级性能比较不管是在应试考试还是在实际应用中算法的性能比较都是我们必会的一项基础技能。那么对于不同量级的时间复杂度他们的时间复杂度性状大小为O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ)记忆口诀常对幂指阶O(1)常数时间操作时间与输入规模无关。O(log n)对数时间常见于二分查找等分治算法。O(n)线性时间操作时间与输入规模成正比。O(n log n)线性对数时间常见于高效排序算法如快速排序、归并排序。O(n²)平方时间常见于简单排序算法如冒泡排序。O(n³)立方时间常见于矩阵乘法等。O(2ⁿ)指数时间常见于暴力搜索算法。实际应用选择小规模数据O(n²)算法可能足够因实现简单。大规模数据需选择O(n log n)或更低复杂度的算法。实时系统优先考虑时间复杂度稳定的算法避免最坏情况下的性能波动。优化策略空间换时间使用哈希表O(1)访问替代线性搜索O(n)。分治策略将问题分解为更小的子问题降低复杂度。剪枝与缓存避免重复计算如动态规划中的备忘录技术。上述优化策略等到后续章节具体情况具体分析。四空间复杂度空间复杂度空间复杂度类似于时间复杂度的定义算法的空间复杂度指算法所需存储空间的度量。记作S(n)O(f(n))在实际分析中我们主要考虑算法使用的额外空间不包括输入数据本身占用的空间。常见的空间复杂度包括O(1)常数空间如交换两个变量的算法O(n)线性空间如需要创建与输入规模相同的数组O(n²)平方空间如某些动态规划算法需要二维数组存储中间结果O(1)的空间复杂度也称之为原地算法。示例递归实现的斐波那契数列的空间复杂度为O(n)因为递归调用栈的深度与n成正比而迭代实现的空间复杂度为O(1)只需要存储前两个值。需要注意的是空间复杂度的分析与时间复杂度类似都是关注增长趋势而非具体数值通常会忽略常数项和低阶项。以上便是本章《数据结构与算法》通识篇的全部内容。欢迎评论指正。作为本系列的第一篇技术类博文有不足之处多多海涵。下一章顺序表的定义及基础操作
