问题的分类

• What：是什么

  面向判断与分类的问题

• why：为什么

  面向求因与证明的问题

• How：怎么做

  面向过程与构建的问题

计算复杂性

• "基于有穷观点的能行方法"的"可计算概念"
  • 仅仅涉及到问题的解决是否能在有限资源内（时间/空间）完成
  • 并不关心具体要花费多少计算步骤或多少存储空间
• 由于资源相当有限，对于问题的解决考虑其可行性如何

计算复杂性与算法

• 计算复杂性理论研究问题的本质，将各种问题按照其难易程度分类，研究各类问题的难度级别，并不关心解决问题的具体方案
• 而算法研究问题在不同现实资源约束情况下的不同解决方案，致力于找到效率最高的方案

抽象与实现

"抽象"发生在各个不同的层次上

• 即使对于程序员来说，使用编程语言进行编程，也会涉及到"抽象"
• 如计算一个数的平方根
  • 可以调用库函数math.sqrt，直接得到结果，而无需关心其内部如何实现
  • 这种功能上的"黑盒子"称作过程抽象Procedural Abstraction

抽象与实现：编程

• 编程是通过一种程序设计语言，将抽象算法实现为计算机可以执行的代码的过程
• 图灵奖获得者Niklaus Wirth的著名公式：

算法+数据结构=编程

• 程序设计语言需要为算法的实现提供实现过程和数据的机制
  • 具体表现为"控制结构"和"数据类型"

大O表示法

算法时间度量指标

• 一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标
  +哪种操作跟算法的具体实现无关？
  +需要一种通用的基本操作来作为运行步骤的计量单位
• 是一个合适的选择
  • 一条赋值语句同时包含了计算和存储两个基本资源
  • 仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理。

问题规模影响算法执行时间

• 问题规模：影响算法执行时间的主要因素
• 算法分析的目标是要找出会怎么影响一个算法的

数量级函数 Order of Magnitude

• 基本操作数量函数T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的部分
  • 用动态的眼光看，就是当问题规模增大的时候，T(n)中的一些部分会盖过其他部分的贡献
• 数量级函数表述了T(n)中随着n增加而增加速度的主导部分
  • 称作“大O”表示法，记作，其中表示T(n)中的主导部分

常见的大O数量级函数

• 通常当m比较小的时，难以确定其数量级
• 当n增长到较大时，容易看出其主要变化数量级

f(n)	名称
1	常数
log(n)	对数
n	线性
n*log(n)	对数线性
n2	平方
n3	立方
2n	指数