3. 函数的增长

本章给出集中标准方法来简化算法的渐进分析。

渐进符号

Θ 渐进紧确界

   $f(n)=\Theta(g(n))$ 类似于 a = b
   当n>n0时，存在常数c₁和c₂使得c₁·g(n) <= f(n) <= c₂·g(n)

Ο 渐进上界

   $f(n)=O(g(n))$ 类似于 a ≤ b
   当n>n₀时，存在一个常数c使得 f(n) <= c·g(n)

Ω 渐进下界

   $f(n)=\Omega(g(n))$ 类似于 a ≥ b
   当n>n₀时，存在一个常数c使得 f(n) >= c·g(n)

ο

   $f(n)=\omicron(g(n))$ 类似于 a < b

ω

   $f(n)=\omega(g(n))$ 类似于 a > b

此图为书中截图，很好的说明了Θ Ο Ω 的含义

留言與分享

2. 算法基础

本章介绍了一个证明算法正确性的方法——循环不变式，对算法运行时间的简单分析，以及分治法。

循环不变式

类似于数学归纳法的一种证明算法正确性的方法。
需要证明以下三步：

• 初始化
  循环的第一次迭代前，它为真。
• 保持
  如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
• 终止
  再循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

分治法

将原问题分解为几个规模较小但类似于原问题的子问题，递归求解这些子问题，然后合并这些子问题的解来建立原问题的解。
每层递归时，都有如下三个步骤：

• 分解
  将原问题分解为几个规模较小但类似于原问题的子问题
• 解决
  递归求解各个子问题，当子问题规模够小可以直接求解时，则直接求解
• 合并
  合并这些子问题的解来建立原问题的解

涉及算法

点击查看实现

• 插入排序
• 归并排序

习题答案

思考题

• 2-4 逆序对

留言與分享

1. 算法在计算中的作用

算法应用广泛，包括解决一些问题，以及让解决一个问题更快速，更省空间。硬件（CPU，内存）总是有限的，所以算法是非常有必要的。不论是当今流行的互联网还是人工智能都和算法息息相关。

算法解决哪些问题

• 基因工程

  DNA中有十万个基因，30亿个化学基对，数据量很大

• 互联网

  管理和处理海量数据（路由，搜索引擎）

• 电子商务

  加密（公钥密码和数字签名）

• 资源分配

  最大利益（线性规划）

• 交通

  导航（最短路径）

• 基因匹配

  最长公共子序列

• 依据部件库的机械设计

  拓扑排序

• 凸壳
• …

难题

NP 完全问题

1. 迄今找不到一个有效算法，但是也没人能证明不存在有效算法
2. 如果任何一个NP 完全问题存在有效算法，那么所有NP 完全问题都存在有效算法
3. 有几个NP 完全问题类似于一些已知有效算法的问题

本书内容

• 算法
• 数据结构
• 算法分析/算法设计

留言與分享