数据结构笔记第二章（算法）

type

status

date

slug

summary

👉 推荐学习资料

《大话数据结构》——程杰

数据结构与算法基础（青岛大学-王卓）_哔哩哔哩

数据结构（浙江大学-陈越、何钦铭）_哔哩哔哩

📝 正文

第二章、算法

2.1 为什么要学习算法？

欸，你有没有发现，我们不是学的是数据结构吗？为什么突然开始讲算法了？

只谈数据结构，我们可以在很短的时间就把几种重要的数据结构介绍完。但是听完后，大概率你对数据结构也只剩下个概念了，你完全不知道这些数据结构有何用处。但如果我们再把相应的算法也拿来讲一讲，你就会发现，这些数据结构的重要性。

当然我们就算谈到算法，也是为了帮助理解好数据结构，并不会详细谈及算法的方方面面。（毕竟有课程专门讲算法，不能抢他饭碗捏 😁）

2.2 算法的定义

什么是算法呢？下面是它的定义：

算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

就拿一个简单的例子举例，1+2+……+100你应该怎么去计算？

最经典的办法便是使用循环去计算：

而伟大的数学家高斯，他却想到一个算法，这便是大家小学便学过的：

那从你的常识判断以下哪种对计算机来说更轻松？

2.3 算法的特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。

输入：算法具有零个或多个输入。有些特殊的算法，不需要任何输入参数，如打印"hello world!" 这样的代码，不需要任何输入参数，因此算法的输入可以是零个。

输出：算法有一个或多个输出。算法是一定要有输出的，不需要输出，你用这个算法干吗?输出的形式可以是打印输出，也可以是返回一个或多个值等。

有穷性：算法必须在执行有限的步骤后结束，并且每一个步骤都必须在有限的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。

确定性：算法的每一个步骤都必须具有确切的含义，不会产生二义性。算法在一定条件下，相同的输入只能有唯一的输出结果。

可行性：算法的每一个步骤都必须是可行的，也就是每一个步骤都可以通过执行有限次的运算完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。

2.4 算法的设计要求

算法的设计要求主要包括正确性、可读性、健壮性和高效性。

正确性：算法能够满足具体问题的需求，在合理的数据输入情况下，能够在有限的运行时间内得到正确的结果。

可读性：算法设计的另一目的是为了便于阅读、理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难于调试和修改。

健壮性：算法应该能对输入数据不合法的情况做适当的处理，而不会产生异常或者莫名其妙的结果。

高效性：高效性包括时间和空间两方面。时间高效是指算法设计合理，执行效率高，即算法运行所消耗的时间短，可以用时间复杂度来度量；空间高效是指算法占用存储空间少，可以用空间复杂度度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

2.5 算法效率的衡量方法

设计算法要尽量提高效率，效率是衡量、比较算法优劣的主要指标。衡量算法效率的方法主要有两类：事后统计法和事前分析估算法。

2.5.1 事后统计法

这种方法主要是先将算法实现，通过设计好的测试程序和数据，利用计算机对不同算法编制的程序测算其时间和空间开销，从而确定算法效率的高低。

但这种方法存在明显缺陷：

必须把算法转换成可执行的程序，这通常需要花费大量的时间和精力。如果这个算法是错误的，那便会“竹篮打水一场空”。

时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的优劣。（低U无显和ROG4090全家桶所测试的效率能一样吗😂）

算法的测试数据设计难度高，因为程序的时空开销往往与测试数据的规模有很大关系。（很多算法是需要非常庞大的数据才能展现出它的优势，编10个数据还好，让你编10亿个数据你承受的了吗🤢）

所以往往会较少采用事后统计法。

2.5.2 事前分析估算法

这种方法指的是在计算机程序编制前，依据统计方法对算法进行估算。

经过分析，我们发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

算法采用的策略、方法。

编译产生的代码质量。

间题的输入规模。

机器执行指令的速度。

第1条当然是算法好坏的根本，第2条要由软件来支持，第4条要看硬件性能。也就是说，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模，所谓问题输入规模是指输入量的多少。

就拿之前举的例子来看：

循环算法：

高斯算法：

显而易见，循环算法一共执行了2n+2次，而高斯算法只执行了2次，谁好谁坏一眼便能看出。

测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。

我们不关心编写程序所用的程序设计语言是什么，也不关心这些程序将跑在什么样的计算机中，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作，最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

2.6 算法时间复杂度

2.6.1 算法时间复杂度定义

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n)). 它表示随问题规模n 的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

2.6.2 算法时间复杂度的分析

分析算法时间复杂度的基本方法：找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号“O”表示即可。在计算算法时间复杂度时，忽略所有低次幂项，只保留最高次幂项，同时忽略其系数，以简化算法分析，也体现了增长率的含义。

而O(1),O(n),O(),O(),O()也分别被称为常数阶，线性阶，对数阶，线性对数阶和平方阶，下面我们来通过几个例子具体去学习时间复杂度的计算。

2.6.2 常数阶

这个算法的执行时间f(n)=3，是一个与问题规模n无关的常数，所以算法的时间复杂度为T(n)=O(1),称为常数阶。注意:不要写成O(3)。

2.6.3 线性阶

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

2.6.4 对数阶

假设循环体内一条基本语句的频度为f(n)，则有2ᶠ⁽ⁿ⁾≤n,f(n)≤log₂n, 所以算法的时间复杂度为T(n)=O(), 称为对数阶。

2.6.5 线性对数阶

内循环中一条基本语句的频度为f(n)=，所以算法的时间复杂度为T(n)=O(),称为线性对数阶。

2.6.6 平方阶

内循环中一条基本语句的频度为 f(n)=n², 所以算法的时间复杂度为 T(n)=O(n²),称为平方阶。

2.6.7 总结

总结一下推导时间复杂度的步骤： 1. 用常数1取代运行时间中的所有加法常数。 2. 在修改后的遥行次数函数中，只保留最高阶项。 3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是时间复杂度。

在多数情况下，当有若干个循环语句时，算法的时间复杂度往往是由最内层循环里的基本语句的频度决定的。

而常见函数的时间复杂度如下图所示:

2.7 最好、最坏和平均时间复杂度

对于人来说，大多数不确定的事情都有最好，最坏的情况，对于代码来说也一样，比如我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为0(1)。但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是0(n),这是最坏的一种情况了。

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。

在后续章节中讨论的时间复杂度，除了特殊说明外，均指最坏情况下的时间复杂度。

2.8 算法的空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(m)=O(f(m)),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。显然我们这章节要讲的重点还是算法的时间复杂度问题。

📎 参考文章

《大话数据结构》——程杰

《数据结构》——陈志贤

💡

欢迎大佬指正笔记中的错误或者不足，对于文中例题有更好的解法也欢迎大佬留言！