算法复杂度是什么?

算法复杂度是指算法在编写可执行程序后,运行时所需要的资源,资源包括时间资源和空间资源。

数据结构和算法本身解决是“”(让程序更加快运行)和“”(让代码省存储空间)的问题,因此,判断算法一个非常重要的考量指标——执行效率(算法执行所需要的时间)。如何来评估算法代码的执行效率,就需要算法复杂度分析(时间和空间复杂度分析)


算法复杂度分析是整个算法的基础,只有掌握它,数据结构和算法的内容基本上掌握了一半。

什么是复杂度:

  1. 数据结构和算法解决是“如何让程序花更少的时间,更少的资源来解决问题”

  2. 算法复杂度由程序执行时间和占用资源这两方面组成,从而评估数据结构和算法的性能

  3. 分别用时间复杂度和空间复杂度来描述算法性能问题,都统称为复杂度

  4. 复杂度是描述算法执行的时间(占用的资源)和数据规模增长的变化趋势

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

  1. 与性能测试相比,算法复杂分析不需要加载实际的数据运行程序,而是通过代码层面估计它运行的时间资源消耗空间资源

  2. 不需要将代码运行一遍,通过统计、监控等得到算法执行时间和占用内存大小,提高开发速度。原因如下:

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

      1. 测试环境中硬件不同会对测试结果有很大的影响,比如同样的代码,分别在内存同样为2g,cpu为inter Core I9和Inter Core I3处理器运行,i9处理器比i3处理器执行的速度更快。

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

      1. 比如从1+2+3+....+100和1+2+3+.....+1000000000运行的速度就不一样。前者可能需要几毫秒,后者在python中运行需要1分钟以上

  3. 掌握复杂度分析,可以更有效找出代码的瓶颈之处,编写出性能更优的代码,降低系统开发和维护成本。

复杂度表示法:O(大O)

O(原本应该读作为omicorn,但我们一般读作“大O”)

1. 如何在不用运行代码的情况下,获取到一段代码的执行时间?如下所示:

假设从cpu角度来看,代码的每个都执行类似的操作:读数据-运算-写数据,每一行代码执行时间都是一样,为unit_time

def cal(n):
    sum = 0 
    i = 1
    for i in range(n):
        sum = sum + i
    return sum

上述代码总执行的时间T(n)是?

  • 第2、3行分别运行时间为1个unit_time

  • 第4、5行分别运行时间为2n(2*n)个unit_time

  • 总执行时间(2+2n)*unit_time

def cal(n):
    sum = 0 
    i = 1
    j = 1
    for i in range(n):
        j = 1
        for j in range(n):
            sum = sum + i * j
    return sum

上述代码总执行时间(T(n))是?

  • 第2,3,4行运行时间为3*unit_time

  • 第5,6行运行时间为2n*unit_time

  • 第7,8行运行时间为2n²*unit_time

  • 总执行时间为(2n²+2n+3)*unit_time

本文地址: http://www.chenxm.cc/article/952.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: 最常见的10个算法
下一篇: ubuntu下各种压缩包的解压命令
发表评论

还没有留言,还不快点抢沙发?