DSA：DataStructure + Algorithm
课程
https://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/
概论
- 什么是计算
- 评判DSA优劣的参照(直尺)
- 度量DSA性能的尺度(刻度)
- DSA性能度量的方法
- DSA的设计及其优化
计算
算法
特定计算模型下，旨在解决特定问题的指令序列
- 输入：待处理的信息 (问题)
- 输出：经处理的信息 (答案)
- 正确性：的确可以解决指定的问题
- 确定性：任一算法都可以描述为一个由基本操作组成的序列
- 可行性：每一基本操作都可实现，且在常数时间内完成
程序未必是算法，如还为证明Hailstone的有穷性
好算法
- 正确
- 符合语法,能够编译、链接
- 能够正确处理简单的输入
- 能够正确处理大规模的输入
- 能够正确处理一般性的输入
- 能够正确处理退化的输入
- 能够正确处理任意合法的输入
- 健壮：能辨别不合法的输入并做适当处理，而不致非正常退出
- 可读：结构化+准确命名+注释+...
- 效率（课程重点）:速度尽可能快;存偷空间尽可能少
度量
-
正确性：算法功能与问题要求一致?数学证明?可不那么简单...
-
成本：运行时间+所需存储空间 如何度量?如何比较?
稳妥起见，在规模同为n的所有实例中，只关注最坏(成本最高)者
图灵机模型
RAM模型
基本操作的次数–>计算时间
分支转向的原理是goto
bigO、bigΩ、bigΘ
至今没有找到多项式时间算法解的一类问题，称之为NP类问题