第3章算法的渐近分析

作者: 橡树人 | 来源:发表于2020-03-25 07:29 被阅读0次

第3章算法的渐近分析
【Python 100天从新手到大师】Python语言进阶
Python-100天(二)-Python语言进阶
算法设计与分析——2.渐进分析与Python计算模型
Python语言进阶
算法和数据结构
算法基础-01.算法复杂度的计算-主定理
算法复杂度基础-主定理
算法设计与分析（第3版）
《算法图解》NOTE 1 算法的渐近表示法以及二分法

有了算法运行时间的增长阶，不仅可以简单的描述算法的效率，而且可以比较算法间的相对性能。比如一旦输出规模n变得足够大，具有最坏情形运行时间 $n\lg{n}$ 的归并排序就从效率上超过具有最坏情形运行时间 $n^2$ 的插入排序。

虽然可确定一个算法的精确运行时间，但是不值得付出努力来计算额外精度。因为对于大规模输入来说，在精确运行时间里的常系数和低阶项可被输入规模自身的影响所控制。所以只需要关心算法的运行时间在规模足够大时的增长阶，即分析当输入规模增长到无穷大时，算法的运行时间是如何增长的，这就是算法的渐近分析。

通常，对于除小规模输入外的所有输入来说，一个渐近意义上更有效率的算法就是最佳选择。

本章给出了若干种用于简化算法渐近分析的方法，主要内容有：

首先，定义若干种渐近记号，比如 $\Theta$ 记号。
接着，介绍若干种在全书里都会使用的记号约定。
最后，回顾下在算法分析中常出现的若干个函数的增长趋势。

第3章算法的渐近分析
有了算法运行时间的增长阶，不仅可以简单的描述算法的效率，而且可以比较算法间的相对性能。比如一旦输出规模n变得足够大...
【Python 100天从新手到大师】Python语言进阶
Python语言进阶数据结构和算法算法：解决问题的方法和步骤评价算法的好坏：渐近时间复杂度和渐近空间复杂度。渐近...
Python-100天(二)-Python语言进阶
数据结构和算法算法：解决问题的方法和步骤评价算法的好坏：渐近时间复杂度和渐近空间复杂度。渐近时间复杂度的大O...
算法设计与分析——2.渐进分析与Python计算模型
2.1引言求解问题的算法往往并不唯一，为了量化不同算法的效率，需要通过渐近分析方法来计算算法的时间复杂度。前一章...
Python语言进阶
Python语言进阶数据结构和算法算法：解决问题的方法和步骤评价算法的好坏：渐近时间复杂度和渐近空间复杂度。...
算法和数据结构
算法和数据结构 [TOC] 算法函数的增长渐近记号用来描述算法渐近运行时间的记号，根据定义域为自然数集$N=...
算法基础-01.算法复杂度的计算-主定理
主定理的定义『在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分...
算法复杂度基础-主定理
在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关...
算法设计与分析（第3版）
《算法设计与分析（第3版）》系统地介绍了算法设计与分析的概念和方法，共4篇内容。第1篇介绍算法设计与分析的基本概念...
《算法图解》NOTE 1 算法的渐近表示法以及二分法
这是《算法图解》的第一篇读书笔记，内容关于表示算法复杂度的渐近表示法以及一个简单但高效的算法：二分法。 1 .渐近...