• 复杂度分析方法
  • 大O复杂度分析法
  • 时间复杂度分析实用方法
  • 几种常见的时间复杂度实例分析
    • 多项式量级
    • 非多项式量级
• Gist code

Hi!

复杂度分析方法

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

###为什么需要复杂度分析

1、测试结果非常依赖测试环境

测试环境中的硬件的不同对测试结果有很大的影响。

2、测试结果受数据规模的影响很大

比如排序算法，排序数据的有序度不一样，排序的执行时间就会有很大的差别。除此之外，如果数据规模太小，测试结果可能无法真实地反应算法的性能。比如对于规模小的数据排序，插入排序可能反而比快速排序要快。

所有我需要一个不用具体的测试数据来测试就可以粗略估计算法的执行效率的方法。

大O复杂度分析法

算法的执行效率粗略的讲就是算法代码的执行时间。尽管每行代码对应的CPU执行的个数、执行的时间不一样，但是我们这里是粗略的估计，所以可以假设每行代码执行的时间都一样，为unit_time。

所有代码的执行时间T(n)与每行代码的执行次数成正比，即T(n) = O(f(n))。 大O时间复杂度表示法，并不具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫做渐进时间复杂度，简称时间复杂度。

时间复杂度分析实用方法

1、只关注循环执行次数做多的一段代码 2、加法法则：总复杂度等于量级最大的那段代码的复杂度 3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

几种常见的时间复杂度实例分析

多项式量级

1、常量阶 O(1)

一般情况下，只要算法中不存在循环的语句、递归的语句，即使有成千上万行代码，其时间复杂度也是O(1) 2、对数阶 O(logn) 3、线性对数阶 O(nlogn)

在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n)) 4、平方阶 O(n^2) 立方阶O(n^3) …. k次方阶O(n^k)

非多项式量级

5、质数阶O(2^n) 6、阶乘阶O(n!) 非多项式量级的算法问题叫作NP(Non-Deterministic Polynomial, 非确定多项式)问题 当数据规模n越来越大的时，非多项式量级算法的执行时间会急剧增加，是非常低效的算法。

Gist code

To use, see:Jektify - Doc

jektify © 2019  +

Música

Jekyll plugin to generate html snippets for embedding Spotify Musics. To listen to the full song, open your Spotify and start these musics.

Goodbye!

---