17复杂度分析

复杂度分析

算法评价的标准：

1.准确性

必须能彻底解决这个问题：使用真实数据的大量测试

2.健壮性

必须保证在任何情况下都不会崩溃

3.效率

3.1运行时间（时间复杂度）

事后统计法的局限性

受到测试环境的制约——不同测试环境对算法的影响不同

数据规模的制约——大量测试数据需要的代价大

复杂度的估计方法

概念：

时间频度：一个算法中，语句执行的次数叫做时间频度T(n)

n就是问题的规模

时间复杂度就是找到T(n)随着规模n变化的规律

一般步骤

1.找到算法中的基本语句（算法中执行次数最多的语句，通常是循环体中的语句），对于顺序结构直接求和。

2.计算基本语句执行次数的数量级（只需计算最高次幂，去除等价无穷小，只关注算法的增长率）

3.使用O来表示算法的时间性能

P类问题——一个多项式时间复杂度能解决的问题

NP类问题——一个指数时间复杂度能解决的问题

如何分析

1.对于简单的输入输出和赋值，近似为O(1)

2.对于顺序结构，求和法则（找到所有顺序结构中的最大值，其余忽略）

3.对于选择结构，计算else字句的时间，也可忽略为O(1)

4.对于循环结构，运行时间主要体现在迭代，乘法法则

5.对于复杂的算法，拆分成简单的结构再计算

对于真实项目所需的分析方法

最好、最坏、平均、摊均

最好与最坏都是极端情况

（加权）平均：所有情况所需的（时间*概率）之和

摊均：大多数情况都是O(1)，少数情况是O(n)——将所有情况摊分

3.2所需内存（空间复杂度）

算法所耗费的空间

在算法中需要临时占用的空间大小（不关注原本需要的空间）