第二章：算法

算法

定义

• 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

特性

• 输入：0或多个
• 输出：1个或多个
• 有穷性
• 确定性
• 可行性

算法设计要求

• 正确性
• 可读性
• 健壮性
• 时间效率高和存储量低

算法效率的度量方法

• 事后统计法：对运行时间进行比较
• 事前估计法

时间复杂度

• 在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。记作：T（n）=O（f（n））
• 大O记法
• T（n）增长最慢的算法是最优算法

推导大O记法

• 常数阶：O（1），例如：O（12）=O（1）

• 线性阶：O（n）

  int i;
  for(i = 0; i < n; i++)
  {
      // TODO
  }
  

• 对数阶：O（logn）

  int count = 1;
  while(count < n)
  {
      count = count * 2;
  }
  

  计算方式：，即，所以

• 平方阶：O（m * n）

  int i, j;
  for(i = 0; i < m; i++)
  {
      for(j = 0; j < n; j++)
      {
          // TODO
      }
  }
  

• 立方阶：O（），例如：

• 指数阶：O（）

• nlogn阶：O（nlogn），例如

耗费时间：O(1)<O(logn)<O(n)<O(nlogn)<O()<O()<O()<O(n!)<O()

空间复杂度

• 定义：以空间换取时间，记作：S（n）= O（f（n））