算法-概述

定义

• Algorithm: 一个有限指令集，每一个指令表示一个或多个操作
• 每一条指令：有充分明确的目标，不可以有歧义；在计算机能处理的范围之内；描述应不依赖于任何一种计算机语言以及具体实现

五个特性

1. 有穷性： 一定在有限步骤之后终止
2. 确定性： 固定的输入产生确定的输出
3. 可行性： 可以通过基本运算有限次执行来实现
4. 有输入： 可能没有
5. 有输出： 一个或多个

重要

学习算法最重要的是学习算法的设计过程（算法思维）， 而不是算法本身，理论要与实践相结合

算法分析

• 指标

1. 空间复杂度S(n) Space

   • 写成的程序在执行时占用存储单元的长度
   • 长度往往与输入数据的规模n有关

2. 事件复杂度T(n) Time

   • 写成的程序在执行时耗费时间的长度
   • 长度往往与输入数据的规模n有关
   • 机器运算加减法要比乘除法要快很多

• 分析一般算法的效率

1. 最坏情况复杂度T_worst(n)

2. 平均复杂度T_avg(n)

   T_avg(n) <= T_worst(n)

3. 所以一般就分析最坏情况复杂度

• 复杂度的渐进表示

算法表示

算法设计策略(一般性方法)

设计算法时正确性，可读性，健壮性，最后考虑高效率和低存储量

• 查找算法

• 排序算法

• 字符串算法

• 分治法

• 动态规划法

• 贪心法

• 回溯法

• 分支限界法

• 概率算法

• 近似算法

• 数据挖掘算法

• 智能优化算法

人工智能相关算法（了解）