数据结构课程中算法复杂度的教学实践研究

冯翱，朱烨，李莉丽

（成都信息工程大学 计算机学院，四川 成都）

一 引言

《数据结构》是计算机学科的核心课程之一，在ACM-IEEE 课程体系中一般被编号为CS2，是在CS1（基础程序设计语言）之后的第二门专业课程。数据结构作为培养程序设计能力的核心专业课程，在问题理解、抽象、设计和实现这个流程中对于计算思维的形成起到关键性作用[1]。由于该课程概念多，并且通常讲解方式较为抽象，如果不能有效地与工程应用结合，对于部分学生来说理解难度较大[2]。

数据结构课程中算法复杂度是最重要的知识点之一[3]，通常在教材的第一章作为基础内容和方法出现。算法复杂度包含时间复杂度和空间复杂度两个概念，分别衡量在一定规模的输入数据下，程序运行时间和额外占用空间相对于问题规模n 的渐近复杂度。前者判断在问题规模较大时，是否能够以比较高的时间效率完成确定性算法的执行，而后者决定算法运行过程中的临时数据是否能够同时在处理效率较高的物理介质中进行操作。通常在数据结构的教学过程中不涉及规模过大的数据集，而且多数算法不会用到超过多项式级别的空间复杂度。除了外部排序（在数据结构课程中一般是选学内容）之外，基本不会发生频繁的内外存数据交换，因此在提到算法复杂度的时候，大多数情况下重点关注的是时间复杂度。

对于算法复杂度分析的应用贯穿于整门课程的教学过程中。后续章节通常是以一类数据结构为核心，讲解其类型定义、在不同存储结构下的实现以及在具体场景中的应用。对于每种物理实现（如顺序或链式存储）下的具体操作，都需要进行时间和空间复杂度分析，一方面是加深学生对于算法过程和资源需求的理解，另一方面复杂度分析决定了在资源受限场景下数据结构和算法选择的优先级和可行性。从某个层面上来说，对于算法复杂度的正确分析决定了学生是否能够真正理解问题的困难程度，并在真实场景中选择适当的算法对其进行合理应用。

二 问题分析

在数据结构课程的教学过程中，算法复杂度的内容相对来说是掌握情况较差的。对于特定逻辑结构下的指定算法，例如标准的内部排序，经过反复的讲解和练习后，大多数学生能够掌握其算法思路，并能在标准化场景下进行应用。但如果要求学生对于特定算法的复杂度进行独立分析，很大一部分的学生不能给出清晰的推导过程和结果，历次考试中算法复杂度分析的题目得分率普遍在50%之下。经过与多届学生的反复沟通，这个知识点掌握困难的主要原因包括概念的抽象性、课程教学中问题规模过小和缺少真实应用案例三方面。

（一） 算法复杂度概念理解上的抽象性

算法复杂度的形式定义是使用数学中的渐近上下界来描述的，以渐近上界的定义为例：

虽然计算机类专业的学生在学习数据结构之前一般都完成了高等数学课程的内容，要求他们用数学的方式阅读并对该公式进行解释，对于绝大多数的学生有很大的困难[4]。相对来说，采用图1 所示的方式直观性地加以解说，对于有一定数学基础的学生来说基本都能够接受。

图1 算法复杂度知识点中渐近上界的图形化说明

对于渐近下界Ω（）和渐近紧确界Θ（）的讲解也有类似的情况。从大多数数据结构教材的内容中可以观察到，虽然多数基本算法在进行复杂度分析时尝试找到的是渐近紧确界，为了降低学生的理解难度，描述复杂度时通常都使用渐近上界符号O（）。

（二） 课程教学中的问题规模

时间复杂度的变化会带来算法运行时间的较大差异，但这个差异一般要在输入数据的大小达到一定规模时才能够被明显观察到。出于教学演示的需求，无论是教材和课件中用到的例子，以DSDemo[5]为代表的算法演示系统，还是课程中设计的实验环节，输入数据集的大小通常不超过20。在这样的小规模数据集上，具有不同运行效率的同类算法在运行时间上没有明显的区别。以内部排序算法为例，虽然我们知道简单排序算法中的冒泡排序具有较高的时间复杂度，而复杂排序算法中的快速排序、堆排序等的平均时间复杂度为，对于实验中用到的小规模数据，实际执行时间都在毫秒级。如果严格执行计时程序，经常会出现简单算法运行更快的结果，这是因为它们单次执行的指令更少，在执行次数差别不大的前提下总的运行时间可能更短。如果在不加限制的条件下要求学生实现一个排序算法，大多数学生毫不犹豫地选择了冒泡排序，主要原因是实现简单。在小规模数据场景下这样的判断并没有错，但在他们毕业进入正式的工程应用环境后，冒泡排序显然不是一个好的默认选项。

（三） 真实工程应用场景的缺失

作为对于真实工程需求的一个介绍，在数据结构课程教学中引入了TeraSort 的例子，这是一个Hadoop 时代的典型案例。随着计算机软硬件的不断发展，Jim Gray 建立的Sort Benchmark 上这个任务已经被MinuteSort 取代，2016 年腾讯的纪录就已经达到一分钟排序37TB（非定制化算法）或55TB（定制优化）数据的水平。但这样规模的数据对于课程教学环节来说，是大大超出学生理解范围的。在类似数据规模下的任何算法问题，对于时间复杂度都会有很高的敏感度。假定单台计算设备有足够的内存，并且编译器支持分配TB 级的内存空间（多数高校的教学设备应该满足不了这些条件），对于不同排序算法的运算时间估计是一个很有意思的问题，而这样来自于真实工程需求的问题对于他们加深对算法复杂度的理解，乃至考虑类似工程问题的算法设计思路都是很有帮助的。在我们的课程教学中，明显缺失了这一部分内容，而这恰恰是学生从书本知识过渡到真实工程需求中欠缺的关键环节。

三 教学环节设计与实施

针对数据结构课程中学生对于算法复杂度理解困难的现状，课程组使用外部数据源和开源框架引入真实数据集，让学生对于大规模问题有直观的感受和更高的参与兴趣，并面向不同层次的学生尝试多种形式、不同规模的项目实践活动，收集了学生的直观反馈，以指导相关知识点教学过程的持续改进。

（一） 外部数据导入

为了在教学环节中让学生有机会接触到更大规模的真实数据，课程组对高校教学领域现有的数据源和访问框架进行了调研。BRIDGES[6]为数据结构课程提供了访问多个真实数据集的简单接口，目前已经包含Twitter、Facebook 等多个数据源，同时为了对于数据有直观的认知，还包含了数据可视化的功能。RealTimeWeb[7]在计算机课程的教学中使用了实时更新的在线数据集，在不接触太多实现细节的前提下让学生熟悉数据处理的基本原理。在计算机领域之外，CORGIS[8]涵盖了历史、政治、医药、教育等多个领域的40 多个数据集。经过对这些框架的调研和比较，选择了最适合相关课程的BRIDGES 框架，经过移植和封装后提供了使用样例和说明文档，供后续项目和其他教学环节使用。

（二） 实践项目设计

数据结构的课程项目设计中给出了一个算法复杂度分析的题目，要求在较大规模的数据集上实现至少一种时间复杂度为和一种复杂度为的排序算法，并且用实验的方法确定其复杂度。为了体现不同复杂度阶次算法之间的性能差异，数据规模要求在10 万条以上，这有效地避免了因为数据量过小导致使用复杂度的简单排序算法运行效率更高的情况。此外，题目要求对于算法真实运行时间或者基本操作执行次数进行记录，让学生能够更直观地感觉到算法选择对于执行效率的影响。虽然这只是一个小规模的实践项目，相对传统课堂上的“小”数据，这是一个更接近于真实工程应用规模的虚拟场景。从提交的结果看来，这个项目一方面对于线性回归、最小二乘法等数学知识提供了额外的学习机会，更有价值的收获是“不仅学会了多种排序算法，更对时间复杂度的概念有了深刻的理解，还把数学知识和编程、算法，联系到了一起，对未来的编程道路有一定的启发作用”。学生从计时结果上真实感受了较大数据规模下时间复杂度算法的明显优势，并有更高积极性去深入分析两类算法的机制差异，尝试理解产生这个复杂度变化的原因。

（三） 算法时间复杂度分析系统

由于数据结构课程在大二上学期设置，学生的数学基础、程序设计能力和对工程问题的理解还比较有限，设计和实现一个具有更高通用性的复杂度分析系统对于这个阶段的学生有一定难度。在本科毕业设计阶段，将《算法时间复杂度分析系统的设计与实现》作为备选题目之一，并提出了更高的要求。增加的主要功能包括：

（1） 对于不同格式、不同来源的输入数据进行读取和清洗，去掉异常数据；

（2） 对于自定义算法，在满足输入输出接口一致的前提下，能够支持复杂度分析功能；

（3） 有效地去除拟合结果中的噪声，得到算法对应复杂度公式中最主要的函数项，该结果在不同设备上具有较好的一致性。

在算法复杂度分析中，对指令/ 代码进行计数是比较常用的方法，但该方法通常只适用于固定代码，对于自定义算法来说难以实现。如果采用运行计时的方法，对于设备的各种参数和运行时负载情况又比较敏感。为了得到跨设备一致的分析结果，学生设计了一段包含主要运算操作的基准代码，用同一设备上算法运行时间和基准代码运行时间的比值作为相对复杂度，这样在一定程度上排除了软硬件环境对于运行时间的影响。针对离群点影响最终拟合结果的情况，又引入了基于M 估计的最小二乘法，保证拟合曲线与实验数据有较好的一致性，系统展示的拟合结果如图2 所示。

图2 归并排序算法在有较多离群点时的拟合结果

学生在对于该系统的总结中提到：“完成的系统表现出良好的拟合效果，得到的曲线与训练数据样本高度重合，并表现出良好的稳定性与可靠性。该系统提供可视化交互式界面，可以对外界的真实数据进行操作，这有利于学生在学习数据结构课程时将教材内容与真实问题接轨，提高学生的学习积极性与参与度。”这与系统的设计目标一致。

四 问题分析与课程改进

从已经实施的教学环节中可以看到，教学过程中的小数据依然是制约学生对算法复杂度深入理解的主要障碍。而要解决这个数据结构课程教学中的共有问题，主要考虑从真实数据、实践案例和师资水平三方面加以改进。

在很多学生的反馈中都提到，当数据规模较小时，不同算法的运行时间差别并不明显，甚至会出现理论复杂度低的算法运行时间更长的情况。当达到一定数据规模之后，不同类别算法的运行时间就明显展示出了增长速度的差异。这也展现了课堂教学和工程应用中的场景特征。在教学环节，如果我们继续使用小规模的“伪”数据，对于学生来说如何用最简单的代码实现要求的功能就会成为他们进行方案选择的第一优先。而在真实工程技术场景下，对于大规模数据进行处理的运行效率直接决定实现方案的可用性。为了弥合二者之间的差异，引入大规模的外部数据，尤其是现实应用中的真实数据，是提高学生工程应用能力的必要环节。

从现在已经尝试的工作来看，算法复杂度至少对于本科低年级学生来说是一个具有一定难度的概念，其原因除了讲解方式较为抽象以外，缺少具有足够规模的真实问题，让他们感受不到复杂度差异对于运行效率的影响，是现有教学过程中不足之处。现阶段工程技术教育逐渐融入到高校教学过程中，这是一个良好的改进契机。不少高校的培养方案中将工程实践、企业实习等纳入本科必修的教学环节，在工程实践教学过程中，可以适当地引入来自企业或者社会的真实数据，并提供将教材所学数据结构和算法应用于真实需求中的实践案例。这对于学生来说，一方面能够更早接触行业需求，了解自己应该学什么，另一方面解决真实问题的成就感远远超过完成教材上的几道习题，对于学习兴趣和动力也会有更大的促进。

对于相关课程的任课教师来说，从校园到校园的纯学术型人才已经不能满足信息学科发展的需求了。获取行业实践经验，根据经济和社会需求相应调整课程教学的内容和手段，也是持续提高教学水平、教学效果和个人能力的需要。此外，在与企业的联合培养过程中引入更多的工程技术型校外导师，也是对于现有以学术型人才为主的高校师资的重要补充。

五 结语

算法复杂度问题在很长一段时间之内都会是数据结构课程的重点和难点之一，主要原因包括渐近复杂度概念的抽象化、课程中使用数据规模过小，以及真实工程应用场景在课程教学环节中的缺失。对于这个概念内涵理解的不够深入使得在课程各阶段的考核中学生的得分率偏低，同时在需要根据问题规模进行算法选择时，很多情况下学生倾向于实现最简单的高复杂度算法，这些都是算法复杂度部分教学效果不佳的直观体现。

为解决这些问题，在本科数据结构课程和毕业论文等几个阶段通过课程项目和毕业设计等方式进行了一些教学模式的实践和研究。从执行情况来看，选择这些项目的学生会有意识地对相关算法、数学基础和算法复杂度分析的方法进行学习，并通过一定规模下的实验真实体会不同复杂度对于算法运行效率的影响。从教师的教学观察和参与学生的直接反馈得知，参与这些教学环节使得学生对于相关概念和方法的理解有一定提高。

基于现有问题和教学研究已取得的成果，为了更为全面地改善数据结构课程中对于复杂度的理解，提高教学效果和在后续工程实践场景中的有意识应用，下一步主要计划从以下几个方面对于培养过程进行改进。

（1） 引入真实外部数据，以增强学习兴趣，并理解真实大数据场景下复杂度对于算法选择和运行效率的影响；

（2） 联合相关企业构建工程实践环节，让学生理解行业真实需求，并有意识地进行按需学习；

（3） 引入具有丰富实践经验的企业导师，并在高校中通过多种方式培养更多的双师型教师，提高整体师资水平，给学生书本知识之外的全方面培养。

算法复杂度只是现有教学模式下暴露出来的一个知识难点，而对应的改进方案也不仅仅是为了解决这一个问题，其核心思路是将学校的培养过程与行业发展和企业所需的知识体系结合，培育面向市场需求的高素质综合型人才。

致谢感谢王维宽提供基于BRIDGES 的外部数据引入代码和文档，感谢在数据结构课程项目中选择算法复杂度题目的吴晶、王奥等同学，感谢李杏作为毕业设计项目完成的算法复杂度分析系统。