一、介绍
- 算法：
- 什么是算法？
算法是解决一类问题或某个计算的过程（方法），算法包含有限步可行的明确的操作。 问题： 2个整数相加（乘）、计算圆周率、计算圆的面积、求一组数中的最大值。 算法接受问题的输入数据、产生输出结果。 问题实例：一类问题的一个具体问题。 “求一组数中的最大值”的问题实例如： 5，2，3，9，4 - 算法解决问题的过程：
设计（定义算法的操作）、 分析（算法的正确性(正确解决问题的需求)、算法的性能（空间和时间消耗））。 - 同一问题可以有不同的算法： 排序
- 算法有什么用（哪些应用）？
```- 是计算机学科的主干：每个计算机科学分支都以算法为核心。 operating systems and compiles：进程调度、词法分析 networking：如路由算法、搜索引擎 machine learning and AI：各种机器学习算法如神经网络层、随机森林、支持向量机、智能算法 cryptography: 密码算法、数论算法 computational biology：动态规划、机器学习 computer Graphics: 计算几何、光照渲染、流体仿真、动画、
- 算法非常有用： 计算速度取决于硬件和算法。 深度学习/现代人工智能、电子商务/自媒体平台的推荐算法、算法决定思维（算法喂料洗脑）。
- 算法有趣： 创造性的数学活动，有趣也有挑战，有挑战才激动人心。如 a^n、大整数乘法 ```
- 什么是算法？
- 算法设计：技术（设计模式）、艺术（创造性思维）
-
算法设计的策略（模式、技术）：
- 穷举法（迭代法）: 列举所有可能情况。求最大值、n!、a^n、斐波拉契数列、平面点集的最近点对。
- 贪婪法: 找零钱、图的Dijsktra最短路径算法
- 分治法: 大问题分解成小问题（Divid），解决小问题(Conqour)、组合小问题解为大问题的解(Combine)
- n!、斐波拉契数列、汉诺塔、大整数相乘、a^n、选择排序、冒泡排序、快速排序、归并排序
- 动态规划:
-
算法的表示（描述）：自然语言、伪代码
-
- 算法分析
- 时间复杂度:最好、最坏、平均
- 空间复杂度
- 渐进分析
- 渐进符号: $O,\Omega,\Theta,o,\omega$
- 递推方程： 迭代展开、递归树、假设验证（数学归纳法）、高阶方程的简化、主定理
- P和NP：算法复杂度和问题复杂度，P问题和NP问题
二、蛮力法、穷举法
- 蛮力法-百钱买百鸡
二、分治递归
- 分治法：
- 思想、分类、算法描述、性能分析
- 选最大与最小：分组、分治递归
- 二分查找、归并排序、汉诺塔
- 幂乘算法及其应用
- 整数乘、矩阵乘：减少子问题的数量
- 快速排序
- 选择问题（第k个）
- 最大子序列和（最大字段和）
- 最近点对
- 棋盘覆盖
- 循环赛日程表
三、动态规划法
- 动态规划 Fibonacci数列、
- 序列比对
- 矩阵链乘法
- 加权区间调度(weighted interval Scheduling)
- 背包问题
- 最长公共子序列
- 最大子序列和（最大字段和）
- 凸三角形最有剖分
- 最优二叉搜索树
- 图像压缩
四、贪婪法
- 活动选择/区间调度（activity selection/Interval Scheduling）
- 找零钱
- 分数背包问题
- 断点选择
- 哈夫曼编码
- 任务调度(task Scheduling)
- Dijkstra最短路径算法
- 最小生成树
五、回溯法与分支定界
- 回溯法
- 图的着色
- 分支定界
- 最大团问题
- 旅行售货员问题
六、网络流算法
- 二部图匹配
- 最大最小切
七、随机算法
- 数值随机化算法
- 舍伍德算法
- 拉斯维加斯算法
- 蒙特卡洛算法
赏
支付宝打赏
微信打赏
支付宝打赏
微信打赏
您的打赏是对我最大的鼓励！
