【算法】算法复杂度分析初步

复杂性分析初步：

计算复杂性体现在算法占用机器空间资源和时间资源的情况，是关于选定模型下输入数据规模的函数。起决定作用的是这些函数当输入数据规模趋于无穷大时的渐进性态。

 主要内容：

1、空间复杂性

2、时间复杂性

3、渐进函数

4、1、2阶递归函数求解

5、the master method

一、空间复杂性：（内存需求）

• 指令空间：存储编译后的程序指令
• 数据空间：存储所以常量和变量的值
• 环境栈空间：保存函数调用返回时恢复运行所需要的信息
• 例子：

二、时间复杂性：（程序运行时间）

• 程序所占时间Tp =编辑时间+运行时间(编译时间与实例特征无关，主要关注运行时间)
• 估算运行时间的方法：

1. 关键操作计数
2. 总的执行步统计

• 约定：每种基本操作所用时间都是一个单位。
• 复杂性函数：f (n), 当它以某一个多项式函数p (n) 为上界时，称为好算法（或叫有效算法）。
• 例子：

1、关键操作计数：选择关键操作，统计次数

平均时间复杂度：

2、统计执行步数：按程序步、执行语句统计

 

例子：

三、渐进函数：

1、渐进上界：

2、渐进下界：

3、渐进同阶：

4、例子：

折半搜索

四、1、2阶递归方程求解

五、The master method