2019.8.30

Software Enegeering

1. Analyze
2. Build
3. Design
4. Verify
5. Analyze
6. Code
7. Test
8. Refine
9. Optimize
10. Maintain

Algorithm - 算法

算法是程序的核心，算法的好坏决定程序的处理效率

• 对数值型数据：主要操作为算数运算
• 对非数值型数据：主要操作为检索、排序、插入、删除等

设计算法的基本过程：

1. 通过对问题进行详细地分析，抽象出相应的数学模型
2. 确定需要的数据结构，在此基础上设计解决问题的方法
3. 使用适当的编程语言将其转换为程序
4. 调试并运行程序，从而解决问题

实验不能证明你的解决方法是对的，只能确定是否可靠
算法可以证明你的解决方法是否对错

算法的特性：

1. 有穷性：算法必须在执行有限步骤后结束
2. 确定性：算法中每一个步骤都有明确的含义，无二义性
3. 可行性
4. 描述

选择算法描述语言的准则：

1. 该语言应具有描述数据结构和算法的基本功能

算法不考虑代码的行数

算法的评价：

• 定性评价：
  • 正确性
  • 健壮性
  • 可读性
• 定量评价：
  • 时间复杂度：是否机器的配置相同，与算法的具体步骤有关
    • 最好情况下：一般不使用该情况
    • 最坏情况下：一般使用该情况
    • 平均 / 概率时间复杂度
  • 空间复杂度：随时代变化，数据的存储

程序所用内存单元数量 = 算法所处理的数据占据的内存单元数量 + 处理数据所需要的额外的内存单元数量

时间复杂度与空间复杂度存在折中情况，牺牲时间换空间，或者牺牲空间换时间

时空复杂度的度量

• 时间复杂度的度量
  • 部分语句例子
    • 赋值语句：O(1)
    • 条件语句1：O(CExp) + O(语句1)
    • 条件语句2：O(CExp) + max(O(语句1)), O(语句2))
    • 开关语句1或2
    • 循环语句：循环次数 + 循环体所用时间
  • 计算法则
    • O(1) + O(1) = O(1)
    • O(1) + O(1) + … + P(1) = O(k)
    • O(1) + O(f(n)) = O(f(n))
    • O(m) * O(n) = O(mn)
    • O(m) - O(m) != O(1) != O(0) [视具体情况而定]

O(1) < O(log n) < O(n) < O(nlogn) < O(n ^ 2) < O(n ^ 3) < O(2 ^ n)
当该算法的时间复杂度的上界与下界相同，则得到最优的算法

基本术语

• 数据
• 数据元素
• 数据项
• 数据对象