11月23日晚，计算机工程系继续开展“双十工程”系列培训，本次培训面向大二同学，主题为算法设计案例之航班冲撞预警。本次培训旨在通过现实案例让同学们切身感受到算法如何提高程序效率。此次培训会由王钧仟老师主讲，90余名2022级计算机科学与技术专业和物联网工程专业学生参与。

QQ群课堂培训会截图

本次培训提前让同学们阅读需求文档并思考了三个问题：1.选择何种数据结构来表示整个澳洲领空。2.如何存储每一个航班的具体位置。3.如何判断冲撞判断。首先，教师就学生的常见解法进行分析。在此过程中，再次温习课堂中所讲的Big-O复杂度知识，强调复杂度不等于运行时间。随后，教师切回到案例，以魔方作为启发提示该案例的底层逻辑，即可以将整个澳洲领空可以抽象成一个巨型魔方，每一个魔方块的体积为1km³，每个航班的位置可以抽象成一个魔方块，当一个魔方块中出现了多架飞机，则冲撞预警触发。

算法设计讲解

接着，教师就学生普遍想到的三维数组表示法进行了分析。三维数组的方法会固定消耗6.38亿个内存单位，存在内存爆炸因此并不能行得通。教师提到这个案例的突破口在于转换视角，从常规的“空间表示视角”切换到“航班视角”，由于题目提到了澳洲领空航班最多两万架次，因此可以从航班角度出发，构造多个并列的一维数组，再以共同索引来分别完成航班添加、航班追踪、航班冲撞检测。同时，在讲解冲撞检测的过程中，重点强调了迭代队列(IterableQueue)的灵活使用。通过算法的升级，内存空间耗费由三维数组状态下的6.38亿降低到了最高8万，避免了内存爆炸。

最后，教师做总结。通过算法的升级和数据结构的创新，此程序由原先的立方级复杂度O(n³)降到了线性级O(n)，不仅解决了内存爆炸的问题，也提高了程序的灵活性，即该航空管理系统可以扩展到任意空域。

通过本次培训，让同学们加强了对算法设计的理解，切身地认识到了算法对于程序的优化和升级，同学们对于课程的认知也有了提高。

智能科技学院：王钧仟

初审：唐学琦

复审：陈婷

终审：常荣

2023年11月23日