张惠艳 陈芳

摘要：基于选择问题的线性时间要求，本文从算法思想、算法实现以及算法复杂度三个部分对《算法设计与分析》课程中“线性时间选择算法”的教学方法进行了探讨，用图形直观地分析了线性时间选择算法的时间复杂度的最好情况和最坏情况，便于学生理解和掌握。

关键词：线性时间选择算法; 二次取中法; 算法复杂度

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2021）35-0260-04

Discussion on the Teaching of Linear Time Selection Algorithm

ZHANG Hui-yan， CHEN Fang

（Huaiyin Normal University， Huaian 223300，China）

Abstract： Based on the linear time requirement of the selection problem， this paper discusses the teaching method of "linear time selection algorithm"in the course of algorithm design and analysis from three parts： algorithm idea， algorithm realization and algorithm complexity. It analyzes the best and worst situation of the time complexity of linear time selection algorithm intuitively with graph， which is convenient for students to understand and master.

Key words： linear time selection algorithm; median of medians rule; algorithm complexity

1引言

《算法设计与分析》是计算机科学与技术专业居于核心地位的专业课程，学生无论是考研究生还是从事IT方面的工作，掌握好这门课的算法理论和算法思想都是非常重要的。这门课不仅要学习基本算法理论，还要用程序设计语言来实现算法，以便学生更好地理解和掌握算法设计的基本方法和技术，有助于学生进一步学习计算机技术，适应更广泛的职业挑战。迄今为止，算法学家们设计了许多基本和经典的算法，如何将这些算法传授给学生，让学生熟练掌握并能运用所学知识解决实际问题，是教授这门学科的教师所面对的主要问题。

大部分高校选用的教材是陈慧楠《算法设计与分析》[1]第二版。教材的算法基本都给出了C++的代码实现，便于学生很好地理解和掌握复杂抽象的算法设计理论。但本课程是一门理论性和实践性都很强的课程，为了取得好的教学效果，很多授课老师都探讨了该课的教学方法[2-8]，提出了自己的教学建议。本文从教学与实践两个环节针对该书的第五章“分治法”中的“线性时间选择算法”谈谈教学体会。……