1、算法的性能测度是必须的
只有知道它现在有多好或者有多烂 才能改进
因此我们引入理想、统一、分层次的尺度
并运用该尺度以测量 DSA的性能
所谓DSA就是数据结构和算法
2、算法分析的标准和方法
两个主要方面是 正确性和成本
正确性主要是数学来解决 数学证明
我们关心的是成本
成本就是运行时间+所需存储空间
那么如何度量 如何比较呢
我们可以用一个实例在这个算法A下的成本来解释算法A的优劣
但是实例太多了 我们用一个实例去替代全部情况总会以偏概全
而在数学上 我们应该 划分等价类
所谓划分等价类 就是把所有的实例进行粗分类
问题的实例规模 往往是决定计算成本的主要因素
当然这未必一定是 大方向是这样的
例如线段三等分的问题
分的段数就是 问题输入的规模
那么很容易理解 随着你要分的段数增多那么计算时间也增多
通常来讲
规模接近,计算成本也接近
规模扩大,计算成本也上升