算法度量

1. 算法的定义

   1. 算法=解法：求解步骤（的描述）
   2. 计算机中表现：指令的有限序列，每条指令表示一个或多个操作

2. 算法的特性（五个基本特性）

   1. 输入、输出
   2. 有穷性
   3. 确定性
   4. 可行性

3. 算法设计的要求

   1. 正确性
   2. 可读性
   3. 健壮性
   4. 时间效率高+存储量低

4. （算法效率的）度量方法

   1. 事前分析估算方法：运行时间预估
      1. 根本：算法（的好坏）
      2. 问题输入(量)规模
      3. ==软件==支持：变异产生的代码质量
      4. ==硬件==性能：机器执行速度
   2. 事后统计方法：计算机计时器对不同算法编制运行时间进行比较

5. 时间复杂度估算效率规范：函数的渐进增长（单调递增）

   1. 忽略加法常数
   2. 忽略最高次项的乘积常数
   3. 关注最高次项的指数（指数大，增长快）

6. 算法时间复杂度

   1. 算法时间复杂度定义：渐近时间复杂度

   2. 【大O记法：O()】推导方法：

      1. O(1)取代所有加法常数
      2. 只保留最高阶项
      3. 最高阶项存在且系数不是1，去除与这个项相乘的系数

   3. 常见的时间复杂度：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

   4. 【最现实】最坏情况&【最理想】平均情况

   5. 算法空间复杂度：S(n)=O(f_(n))