目 录 Contents 第1单元 堆栈队列.......................................................... 0011.1 认识数据结构.................................................................. 002 1.2 堆栈 ................................................................................ 003 1.3 队列 ................................................................................ 009 1.4 堆栈和队列的基本应用 ................................................... 012 习题......................................................................................... 017 第2单元 算法分析.......................................................... 0192.1 计算的复杂性.................................................................. 020 2.2 时间复杂度 ..................................................................... 021 2.3 空间复杂度 ..................................................................... 029 2.4 优秀算法的评价标准....................................................... 032 习题......................................................................................... 033 第3单元 排序算法..........................................................0353.1 冒泡排序......................................................................... 036 3.2 选择排序......................................................................... 039 3.3 直接插入排序.................................................................. 042 习题......................................................................................... 045 第4单元 查找算法..........................................................0474.1 顺序查找......................................................................... 049 4.2 二分查找......................................................................... 051 4.3 插值查找......................................................................... 055 习题......................................................................................... 059 Gwszw四级1-7.indd 7 2023/9/13 9:51:38 第5单元 匹配算法.......................................................... 061 5.1 字符串暴力匹配算法（BF 算法） ...................................062 5.2 字符串匹配KMP 算法.....................................................064 5.3 字符串匹配BM 算法.......................................................071 习题.........................................................................................076 第6单元 蒙特卡罗算法..................................................078 6.1 蒙特卡罗算法简介 ..........................................................079 6.2 蒙特卡罗算法的应用.......................................................081 习题.........................................................................................085 第7单元 分形算法..........................................................087 7.1 大自然中的分形几何.......................................................088 7.2 Koch 曲线的递归算法.....................................................091 7.3 分形树的递归算法 ..........................................................094 7.4 牛顿迭代算法..................................................................096 习题.........................................................................................102 第8单元 聚类算法.......................................................... 103 8.1 认识聚类.........................................................................104 8.2 鸢尾花分类 .....................................................................106 8.3 分散性聚类算法（K-means）.........................................107 8.4 基于层次的聚类算法(AGNES) ........................................114 8.5 基于密度的聚类算法(DBSCAN)......................................118 习题.........................................................................................124 第9单元 预测算法.......................................................... 126 9.1 普通线性回归预测算法 ...................................................127 VIII Gwszw四级1-7.indd 8 2023/9/13 9:51:53 9.2 岭回归预测算法 ..............................................................133 9.3 Lasso 回归预测算法 .......................................................137 习题.........................................................................................141 第10单元 调度算法........................................................ 143 10.1 进程调度.......................................................................144 10.2 先来先服务调度算法.....................................................145 10.3 短作业优先调度算法.....................................................147 10.4 优先级调度算法 ............................................................151 习题.........................................................................................156 第11单元 分类算法......................................................... 158 11.1 支持向量机分类算法.....................................................160 11.2 K-最近邻算法...............................................................161 11.3 随机森林算法................................................................163 习题.........................................................................................169 第12单元 路径算法......................................................... 171 12.1 路径算法概述................................................................172 12.2 迪杰斯特拉算法 ............................................................174 12.3 弗洛伊德算法................................................................179 12.4 SPFA 算法.....................................................................186 习题.........................................................................................189 附录A 人工智能及机器学习基础..................................... 191