美文网首页
复杂度分析---快和省

复杂度分析---快和省

作者: 星丶雲 | 来源:发表于2019-09-17 10:39 被阅读0次

一、什么是复杂度分析?

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。

2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。

3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。

4.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

二、为什么要进行复杂度分析?

1.和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

三、如何进行复杂度分析?

1.大O表示法

1)来源

算法的执行时间与每行代码的执行次数成正比,用T(n) = O(f(n))表示,其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。

2)特点

以时间复杂度为例,由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

2.复杂度分析法则

1)单段代码看高频:比如循环。

2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。

3)嵌套代码求乘积:比如递归、多重循环等

4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

四、常用的复杂度级别?

多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,

O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)

非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,

O(2^n)(指数阶)、O(n!)(阶乘阶)

五、如何掌握好复杂度分析方法?

复杂度分析关键在于多练,所谓孰能生巧。

相关文章

  • 算法复杂度分析

    复杂度分析: 数据结构和算法解决的两大问题:快和省。运行快,储存省。 复杂度分析是算法学习的精髓:时间复杂度,空间...

  • 复杂度分析---快和省

    一、什么是复杂度分析? 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时...

  • 复杂度分析(上)

    复杂度分析(上) 如何分析、统计算法的执行效率和资源消耗 数据结构和算法解决的是快 和 省的问题复杂度分析是整个算...

  • 2021-05-12

    数据复杂度分析 数据结构和算法本身解决的快和省的问题; 如何衡量的代码的执行效率;时间、空间复杂度分析。 1. 测...

  • 2. 复杂度分析:如何分析、统计算法的执行效率和资源消耗?

    数据结构和算法本身就是解决"快"和"省"的问题,即如何让代码运行的更快,让代码更省存储空间。复杂度分析,是整个算法...

  • Java数据结构和算法(二)时间、空间复杂度分析

    1、为什么需要复杂度分析? 数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省...

  • 复杂度分析(分享)

    1、复杂度分析 数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,更省存储空间。执行效率是算...

  • 2020-08-07复杂度分析上

    复杂度分析的目的   数据结构与算法本身是为了解决快和省的问题,所以执行效率是衡量算法好坏的一个非常重要的指标,...

  • 算法-复杂度分析

    问题一:为什么要做算法的复杂度分析。算法的本质就是一个快与省的问题,如何用最快的速度和最小的内存空间出处理某件事情...

  • 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?

    03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗? 我们都知道,数据结构和算法本身解决的是“快”...

网友评论

      本文标题:复杂度分析---快和省

      本文链接:https://www.haomeiwen.com/subject/fkmquctx.html