ADT

抽象数据类型（ADT）是一个实现包括储存数据元素的存储结构以及实现基本操作的算法。

  1. ADT {
  2.   数据对象: (数据元素集合)
  3.   数据关系: (数据关系二元组结合)
  4.   基本操作: (操作函数的罗列)
  5. }

算法

算法是指解决问题的一种方法或者一个过程

  1. 正确性。它必须完成所期望的功能
  2. 具体步骤。一种算法应该由一系列具体步骤组成。
  3. 确定性。下一步应执行的步骤必须明确
  4. 有限性。一种算法必须有有限步骤组成
  5. 可终止性。算法必须可以终止

数学归纳法

  1. 初始情况: n = c时 Thrm 成立
  2. 归纳步骤：如果 n - 1 时 Thrm 成立，则 Thrm 对于 n 也成立
  3. 如果对于所有满足条件 c <= k < n 的 k,Thrm 都成立，则 Thrm 对于 n 也成立

程序运行时间的计算

  1. while循环与for循环类似
  2. if语句最差的情况时间代价是then和else语句中时间代价较大的那一个
  3. switch语句的最差情况时间代价是所有分支中开销最大的那一个

事前分析估算方法

在计算机程序编写前，依据统计方法对算法进行估算

  1. 算法采用的策略和方案
  2. 编译产生的代码质量
  3. 问题的输入规模
  4. 机器执行指令的速度

评估

  1. 确定影响问题的主要参数
  2. 推导出一个与问题的参数有关的公式
  3. 选择参数值，由该公式得出一个评估解

推导大O阶方法

  1. 用常数1取代运行时间中所有的加法常数
  2. 在修改后的运行次数函数中，只保留最高阶项
  3. 如果最高阶项存在且不是1，则去除渔哥这个项相乘的常数