精华内容
下载资源
问答
  • 算法时间复杂度的计算
    千次阅读
    2019-08-25 16:48:57

    一、算法时间复杂度定义

            在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n的函数,进而分型T(n)随着n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量记作:T(n)=O(f(n)).它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度.其中f(n)是问题规模n的某个函数.

    简单来说T(n)代表时间频度:一个算法中语句执行次数称为时间频度

    时间复杂度就是:算法的时间复杂度描述的是T(n)的变化规律,计作:T(n) = O(f(n))。

    这里用大写的O( )来体现算法时间复杂度的记法,我们称之为大O记法.


    二、推导大O阶方法(游戏秘籍三部曲)

    1. 用常数1取代运行时间中的所有加法常数。
    2. 在修改后的运行次数函数中,只保留最高阶项。
    3. 如果最高阶项存在且不是1,则去除与这个项乘积的常数。

    三、常数阶

    let sum = 0, n = 100  //执行一次
    sum = (1 + n) * n / 2  //执行一次
    return sum //执行一次

    这个算法的运行次数是f(n)=3,与n的大小无关
    根据推导大O阶的方法,常数项3改为1,即时间复杂度为O(1)
    对于分支结构(不含循环结构),无论真或假,执行的次数都是恒定的
    不会随着n的变大而发生变化,其时间复杂度也是O(1)

    四、线性阶

    for(let i=0;i<n;i++){
       
       /* 这里是时间复杂度为O(1)的程序步骤序列*/
    
    }

    关键就是要分析循环结构的运行情况
    上面这是一个for循环,那么它的时间复杂度又是多少呢?首先循环体就是一个执行一次的循环体,总共执行了n次,那么执行次数就是f(n) =n,启动我们的游戏攻略三部曲知道,时间复杂度就是为O(n).

    五、对数阶

    let count=1;
    while(count<n){
        count=count*2
    }

    对数阶不是很好理解
    每次count都会乘以一个2,他会距离n更近一步
    这里详细解释一下
    count=1时 1<n count=2 2的一次方
    count=2时 2<n count=4    2的二次方
    count=4时 4<n count=8    2的三次方

    到2的x次方大于n的时候 循环就结束了
    由2的x次方等于n --> x = logn,时间复杂度为O(logn)
    常见的二分查找就是以上思路,时间复杂度为O(logn).

    六、平方阶

    for(let i=0;i<n;i++){
        for(let j=i+1;j<n;j++){
            
         /* 这里是时间复杂度为O(1)的程序步骤序列*/
    
        }
    }

    由于当i = 0时,内循环执行n此,当n = 1时, 执行了 n - 1 次, …当 i = n-1 时, 执行了1次,所以总的执行次数为:
    n + (n -1) +( n -2 ) +… +1 = n(n +1)/2 = n^2/2 + n/2

    根据我们的游戏秘籍的三部曲(保留最高阶,去除最高阶不是1的常数项),我们可以分析出来,时间复杂度为 O( n^2 ).

    七、常见算法时间复杂度

     

    笔者最近看《大话数据结构》,总结了一点,最后一张图网上找的。需要《大话数据结构》pdf高清电子版的铁汁留言,我在评论区发你!

    更多相关内容
  • 算法时间复杂度

    2017-11-02 22:28:24
    算法时间复杂度
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 所有算法时间复杂度对比、图表形式、函数关系
  • 选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
  • 应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、...
  • Dijkstra算法时间复杂度分析

    万次阅读 多人点赞 2021-02-24 20:35:04
    之前一直默认Dijkstra算法时间复杂度为 o(n2)o(n^{2})o(n2),没有思考过具体的时间复杂度,今天把这个弄清楚。 Dijkstra算法的思路与关键点 思路:广度优先 + 松弛 所有点分为两个集合SSS和TTT,SSS最开始只包括...


    之前一直默认Dijkstra算法时间复杂度为 o ( n 2 ) o(n^{2}) o(n2),没有思考过具体的时间复杂度,今天把这个弄清楚。

    Dijkstra算法的思路与关键点

    • 思路:广度优先 + 松弛
    1. 所有点分为两个集合 S S S T T T S S S最开始只包括源点 s s s,剩余点都位于 T T T S S S集合表示已经计算出最短路径的点集合, T T T表示尚未计算出最短路径的点集合。
    2. 每次从集合 T T T中选出一个与集合 S S S距离最短的点 v v v,将点 v v v加入集合 S S S。通过点 v v v对集合 T T T中的点进行松弛,即更新 T T T中点的最短距离。
    3. 不断重复此步骤2,直至T集合中无法找出与集合 S S S相邻的点。
    • 关键点:每次从 T T T中选出的点,距离源点的距离一定不会被松弛,因此每次选出的点都将加入集合 S S S.。

    Dijkstra算法的时间复杂度

    设图中的节点数为 n n n,边个数为 m m m,平均每个点的边数 k = m / n k=m/n k=m/n

    算法步骤2需要执行 n − 1 n-1 n1次,每次从集合 T T T中选出一个与集合 S S S相距最近的点,具体实现方式有4种。

    • 顺序遍历集合 T T T
    • 使用二叉堆作为优先队列
    • 使用二项堆作为优先队列
    • 使用斐波那契堆作为优先队列

    前提知识:二叉堆,二项堆,斐波那契堆的各种操作时间复杂度
    在这里插入图片描述

    对于Dijkstra算法,给出时间复杂度的计算公式
    ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) (n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) (n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)

    下面对于上述四种方式,分别计算其时间复杂度。

    1. 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( n + 1 + k ) = n ∗ ( n + k ) = n 2 + m = n 2 \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(n+1+k)\\ &=n*(n+k)\\ &=n^{2}+m &=n^{2} \end{aligned} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(n+1+k)=n(n+k)=n2+m=n2
    2. 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( 1 + log ⁡ n + k ∗ log ⁡ ( n ) ) = n ∗ ( 1 + k ) log ⁡ n = ( n + m ) log ⁡ n \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(1+\log{n}+k*\log(n))\\ &=n*(1+k)\log{n}\\ &=(n+m)\log{n} \end{aligned} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(1+logn+klog(n))=n(1+k)logn=(n+m)logn
    3. 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( log ⁡ n + log ⁡ n + k ∗ log ⁡ ( n ) ) = n ∗ ( 2 + k ) log ⁡ n = ( 2 n + m ) log ⁡ n = ( n + m ) log ⁡ n \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(\log{n}+\log{n}+k*\log(n))\\ &=n*(2+k)\log{n}\\ &=(2n+m)\log{n}\\ &=(n+m)\log{n} \end{aligned} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(logn+logn+klog(n))=n(2+k)logn=(2n+m)logn=(n+m)logn
    4. 时 间 复 杂 度 = ( n − 1 ) ∗ ( T E X T R A C T − M I N + T D E L E T E + T D E C R E A S E − K E Y ∗ k ) = ( n − 1 ) ∗ ( log ⁡ n + log ⁡ n + k ∗ 1 ) = n ∗ ( 2 log ⁡ n + k ) = 2 n log ⁡ n + m = n log ⁡ n + m \begin{aligned} 时间复杂度&=(n-1)*(T_{EXTRACT-MIN}+T_{DELETE}+T_{DECREASE-KEY}*k) \\ &=(n-1)*(\log{n}+\log{n}+k*1)\\ &=n*(2\log{n}+k)\\ &=2n\log{n}+m\\ &=n\log{n}+m\\ \end{aligned} =(n1)(TEXTRACTMIN+TDELETE+TDECREASEKEYk)=(n1)(logn+logn+k1)=n(2logn+k)=2nlogn+m=nlogn+m
    展开全文
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 算法时间复杂度分析(一)

    万次阅读 2019-07-03 22:50:59
    具体点来讲就是我们在实现某一种算法的时候,最终目的就是要求计算机(CPU)在最短的时间内,用最少的内存稳定的输出正确的结果。这一章节主要来理解 “快”,至于“省” 和 “稳”,我会在后续章节进行讲解。 那如何...

    金庸武侠中描述一种武功招式的时候,经常会用到 “快、准、狠” 这3个字眼。同样,在计算机中我们衡量一种算法的执行效率的时候也会考量3个方面:“快、省、稳”。

    具体点来讲就是我们在实现某一种算法的时候,最终目的就是要求计算机(CPU)在最短的时间内,用最少的内存稳定的输出正确的结果。这一章节主要来理解 “快”,至于“省” 和 “稳”,我会在后续章节进行讲解。

    那如何来判断某一段代码运行的是否足够快呢??有没有一种标准让我们能迅速判断出某A算法比某B算法好呢??大O复杂度表示法 就是我们要寻找的答案,一般情况下,大O复杂度表示法是用来表示算法性能最常见的正式标记法,接下来就一起来看下这个大O复杂度表示法是个什么东东。

    算法时间复杂度的由来

    在理解什么是时间复杂度之前,我们需要先了解为什么需要复杂度分析。为了更形象的理解这个问题,我们用一段具体的代码来深入分析。这里有段非常简单的代码,实现了 1,2,3…n 的累加和。

    案例1:
    // 计算 1, 2, 3…n 的累加和
    public class Test {
        int cal(int n) {
            int sum = 0;
            int i = 1;
            for (; i <= n; ++i) {
                sum = sum + i;
            }
            return sum;
        }
    }
    

    如果我们要测试以上面这段代码的执行效率,该如何去测试呢 ??

    起初,我们能想到最简单最直接的方法就是把代码在机器上跑一遍,通过统计、监控,就能得到这段代码所执行的时间和占用的内存大小。既然是这样那为什么还要做时间、空间复杂度分析呢?复杂度分析会比我实实在在跑一遍得到的数据更准确吗?

    首先,我可以肯定的说,这种评估算法的执行效率是正确的,并且在某些数据结构和算法的书籍中还专门给这种方法起了个名字—事后统计法。但是这种统计方法有非常大的局限性

    1 测试结果极度依赖测试环境
    测试环境中的硬件不同会对测试结果有很大的影响。比如案例1的代码分别跑在Intel Core i9 和 Intel Core i3的CPU上运行,很明显i9要比i3快很多。再比如我们在同一时刻在i9上执行运算1024/3,并在i3上运算10+10。正常来讲 10+10 操作比 1024/3 的操作简单很多,但是因为硬件性能的影响,导致i9处理器更快的得出结果。难道我们能说 1024/3 比 10+10 算法性能更高?显然不能!即使是一个初级工程师也应该知道除法运算比加法运算消耗更高!这样就造成我们很难用一个统一的标准去衡量执行时间。

    2 测试结果受数据规模的影响很大
    后续我们会讲到多种排序算法。对于同一种排序算法,比如快速排序或者插入排序,待排序数据的有序度不一样,排序的执行时间就会有很大差别。另外,对于不同的排序算法,测试数据规模不同也可能导致无法真实的反应排序的性能。比如,我们手上有一组小规模的数据需要做排序操作
    int arr[] = {4, 10, 42, 1, 9};
    如果分别使用插入排序和快速排序对 arr 进行排序,我们会发现插入排序比快速排序更快。但是这样不能说明插入排序的性能就比快速排序更高。因为随着arr规模的增长,它的性能会越来越低于快速排序。

    综上所述,我们需要一个不用具体的测试数据来测试,用“肉眼”就可以粗略的估计算法的执行效率的方法。而这种方法就是我们今天要讲的 时间复杂度分析方法


    代码复杂度的分析过程

    算法的执行时间等于它所有基本操作执行时间之和, 而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积,如下:

    算法的执行时间 = 操作1 + 操作2 + ... + 操作n
    操作的执行时间 = 操作执行次数 * 执行一次的时间
    

    我们还是以案例1的代码为例。我们知道java代码经过编译之后,最终会被以字节码的方式由JVM来解释执行相应的指令,那我们可以通过如下命令,分别对Test.java进行编译并查看字节码

    javac Test.java    // 编译java代码,生成.class字节码文件
    javap -c Test      // 使用javap工具查看字节码指令
    

    执行上述的javap命令之后,得到的字节码指令如下:
    在这里插入图片描述
    可以看出,案例1主要包含的字节码指令就是 iconst_ istore_ iload_ if_icmpgt iadd 等指令,具体每一条指令所代表的意义我已经添加注释(这块内容有点多,但建议耐心仔细阅研读一下,彻底理解每一条指令的意义,也有助于你理解Java代码的运行机制)

    然而存在一个问题,不同的编程语言,不同的编译器,或不同的CPU等因素将导致执行一次指令操作的时间各不相同,这样的结果会使算法的比较产生歧义, 于是我们假定所有计算机执行相同的一次指令操作所需时间相同,统一定为 unit_time 。而把算法中基本操作所执行的 执行次数n 作为量度。就是说我们把算法的 运行时间 简单地用基本操作的 运行次数 来代替了, 进而将分析 运行时间 转移到某一行代码的 运行次数

    其中unit_time在不同的CPU上可能不一样,比如在i9 Core上有可能是0.01ms,而在i3 Core上可能就是0.05ms。在这个假设的基础上,我们就可以计算出这段代码的总执行时间。

    字节码指令是自上而下顺序执行的,所以从指令0开始执行。0-3指令都执行一遍,也就是 **unit_time * 4** 。从指令 4 到指令 19,从图中两个红色箭头也能看出存在循环操作,而

    循环的依据就是if_icmpgt指令。

    if_icmpgt 指令判断的是操作数栈顶的两个元素的大小,也就是 i 与 n 的大小,因为从指令 4 到指令 19 一共包含10条指令,所以4~19的指令执行次数为:10 * n * unit_time

    综上所述,这段代码总的执行时间就是:

    4 * unit_time + 10 * n * unit_time
    = (10n + 4) * unit_time

    按照这个分析思路,我们再来看下面这段代码。

    案例2
    void cal(int n) {
       int sum = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1;
         for (; j <= n; ++j) {
           sum = sum +  i * j;
         }
       }
    }
    

    案例2的代码与案例1的唯一区别就是多了一层for循环。经过javac和javap之后的字节码指令如下:
    在这里插入图片描述

    分析过程同案例1的一样,具体就不再赘述了。最终分析案例2总的执行时间为:(45n² + 5n + 5) * unit_time

    算法时间复杂度表示法

    上面我们通过分析字节码指令,计算出案例1和案例2代码片段的具体运行时间,如下:

    案例1运行时间 -> (10n + 4) * unit_time
    案例2运行时间 -> (45n² + 5n + 5) * unit_time

    尽管我们不知道 unit_time 的具体值,但是通过对案例1和案例2代码执行时间的推导过程,我们可以得到一个非常重要的规律,那就是 所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

    我们可以把这个规律总结成一个公式,注意,大O要登场了
     T(n) = O(f()n)
    

    来解释一下这个公式:T(n)表示代码的执行时间;n表示数据规模的大小;f(n)是一个函数,表示每行代码执行的次数总和。函数f(n)外部的大O表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

    注意:大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,
    也叫作渐进时间复杂度(aymptotic time complexity),简称时间复杂度。或者说它表达的是随着数据规模n的增长,代码执行时间的增长趋势(类似于物理中的加速度)

    既然大O表示的是一种增长趋势而不是具体时间,那在我们先前计算出的等式中的 unit_time 也就没什么太大意义了。所以,我们可以将等式中的 unit_time 去掉。

    案例1运行时间 -> (10n + 4) *unit_time
    案例2运行时间 -> (45n² + 5n + 5) *unit_time

    最终案例1中的 T(n) = O(10n + 4),案例2中的 T(n) = O(45n² + 5n + 5)这就是大 O 时间复杂度表示法

    现在我们了解了大O表示法的演进过程,接下来我们再把视线重新放到案例2的复杂度表示上 T(n) = O(45n² + 5n + 5),细看之下,此表达式的函数f(n)部分由3部分组成 (45n² 高阶项) 、 (5n 低阶项) 、 (5 常数项)

    现在我们假设 n = 3 时

    45n² 高阶项 : 45 * 3 * 3 = 405 占总时间的 95.29%
    5n 低阶项 : 5 * 3 = 15
    5 常数项 : 5

    我们已经看到,n²高阶项部分占据了运行时间的大部分比例。

    现在,考虑当n = 100时的结果,如下

    45n² 高阶项 : 45 * 100 * 100 = 4500 占总时间的 99.98%
    5n 低阶项 : 5 * 10 = 50
    5 常数项 : 5

    可以看到,n²的部分已经占据了几乎整个运行时间,同时其它项的影响力变得更小,试想一下,如果n = 1000, 将占用多少时间!

    由此我们可以看出,当我们以增长率的角度去观察 f(n) 函数的时,有几件事就变得很明显:

    • 首先,我们可以忽略常数项,因为随着n的值变得越来越大,常数项最终变得可忽略不计
    • 其次,我们可以忽略系数
    • 最后,我们只需要考虑高阶项的因子即可,不需要考虑低阶项

    综上所述:案例1和案例2的终极大O时间复杂度表达式可以简化为:

    案例1: T(n) = O(10n + 4) = O(n) // 时间复杂度为线性级别
    案例2: T(n) = O(45n² + 5n + 5) = O(n²) // 时间复杂度为指数级别

    时间复杂度简单规则:

    前面介绍了大 O 时间复杂度的由来和表示方法。现在我们来看下,当我们拿到一段代码时,如何去分析这一段代码的时间复杂度?

    以下是几个比较实用的方法,你可以参考一下:

    1 只关注循环执行次数最多的一段代码

    我刚才说了,大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。

    所以,我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码即可。这段代码执行次数的n的量级,就是争端要分析代码的时间复杂度。

    为了便于你理解,我还拿前面的例子来说明。

    int cal(int n) {
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
         sum = sum + i;
       }
       return sum;
    }
    

    其中第 2、3 行代码都是常量级的执行时间,与 n 的大小无关,所以对于复杂度并没有影响。循环执行次数最多的是第 4、5行代码,

    所以这块代码要重点分析。前面我们也讲过,这两行代码被执行了 n 次,所以总的时间复杂度就是 O(n)。

    2 加法法则:总复杂度登记量级最大的那段代码的复杂度

    我这里还有一段代码。你可以先试着分析一下,然后再往下看跟我的分析思路是否一样

    int cal(int n) {
       int sum_1 = 0;
       int p = 1;
       for (; p < 100; ++p) {
         sum_1 = sum_1 + p;
       }
       int sum_2 = 0;
       int q = 1;
       for (; q < n; ++q) {
         sum_2 = sum_2 + q;
       }
       int sum_3 = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1;
         for (; j <= n; ++j) {
           sum_3 = sum_3 +  i * j;
         }
       }
       return sum_1 + sum_2 + sum_3;
    }
    

    这个代码分为三部分,分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度,然后把它们放到一块儿,再取一个量级最大的作为整段代码的复杂度。

    第一段的时间复杂度是多少呢?这段代码循环执行了 100 次,所以是一个常量的执行时间,跟 n 的规模无关。

    这里我要再强调一下,即便这段代码循环 10000 次、100000 次,只要是一个已知的数,跟 n 无关,照样也是常量级的执行时间。当 n 无限大的时候,就可以忽略。尽管对代码的执行时间会有很大影响,但是回到时间复杂度的概念来说,它表示的是一个算法执行效率与数据规模增长的变化趋势,所以不管常量的执行时间多大,我们都可以忽略掉。因为它本身对增长趋势并没有影响。

    那第二段代码和第三段代码的时间复杂度是多少呢?答案是 O(n) 和 O(n2),你应该能容易就分析出来,我就不啰嗦了。

    综合这三段代码的时间复杂度,我们取其中最大的量级。所以,整段代码的时间复杂度就为 O(n2)。也就是说:总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是:

    如果 T1(n)=O(f(n)),T2(n)=O(g(n));
    那么 T(n) = T1(n)+T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))

    3 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    我刚讲了一个复杂度分析中的加法法则,这儿还有一个乘法法则。当分析一个算法的运行时间时,如果一个任务的执行引起了另一个任务的执行,可以运用此规则。例如,在一个嵌套循环中,外层迭代为T1, 内层迭代为T2, 如果T1 = m, T2 = n, 那么运行结果表示为O(m * n)。

    落实到具体的代码上,我们可以把乘法法则看成是嵌套循环,我举个例子给你解释一下

    int cal(int n) {
       int ret = 0;
       int i = 1;
       for (; i < n; ++i) {
         ret = ret + f(i);
       }
    }
    int f(int n) {
      int sum = 0;
      int i = 1;
      for (; i < n; ++i) {
        sum = sum + i;
      }
      return sum;
    }
    

    我们单独看 cal() 函数。假设 f() 只是一个普通的操作,那第 4~6 行的时间复杂度就是,T1(n) = O(n)。但 f() 函数本身不是一个简单的操作,它的时间复杂度是 T2(n) = O(n),所以,整个 cal() 函数的时间复杂度就是,

    T(n) = T1(n) * T2(n) = O(n*n) = O(n²)。

    我刚刚讲了三种复杂度的分析技巧。不过,你并不用刻意去记忆。实际上,复杂度分析这个东西关键在于“熟练”。你只要多看案例,多分析,就能做到“无招胜有招”。

    总结

    这一节我们首先学习了为什么要使用算法复杂度分析,主要是因为外部硬件环境与数据规模不一样,会导致我们的计算结果出现偏差。因此需要一套不依赖具体测试数据的机制来衡量算法的性能。

    接下里我们通过分析两个案例代码的粗略执行时间,进而引出了大O复杂度表示法,它是一种正式的表达算法时间复杂度的表示法。需要注意的是大O表达式并不表示某种算法具体的运行时间,而是表示代码执行时间随数据规模增长的变化趋势。

    最后我总结了几点分析代码复杂度时的简单规则,或者说是技巧。通过这些技巧有助于我们更快的分析出某一段代码的时间复杂度时多少。

    更多文章可以扫描二维码,关注算法公众号

    展开全文
  • 1. 时间复杂度时间复杂度是指程序运行从开始到结束所需要的时间。...基本操作应是其重复执行次数和算法时间成正比的原操作,多数情况下它是最深层循环内的语句中的操作。算法的执行次数还要随输入...

    1. 时间复杂度

    时间复杂度是指程序运行从开始到结束所需要的时间。时间复杂度的计算一般比较麻烦,故在数据结构的研究中很少提及时间复杂度。为了便于比较同一个问题的不同算法,通常做法是,从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数做为算法的时间量度。基本操作应是其重复执行次数和算法时间成正比的原操作,多数情况下它是最深层循环内的语句中的操作。算法的执行次数还要随输入集有关,此时要考虑所有可能输入数据的期望值,此时的算法时间复杂度叫平均时间复杂度。有事平均时间复杂度难以确定,此时分析最坏情况下算法的一个上界,此时称为最坏时间复杂度。

    2. 时间复杂度的表示方法

    设解决一个问题的规模为n,基本操作被重复执行次数是n的一个函数f(n),则时间复杂度可记作: T(n)=O(f(n)) 它表示随着问题规模n的增长,算法执行时的增长率和f(n)的增长率相同。其中T(n)叫算法的渐进时间复杂度,简称时间复杂度。算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以精确计算的情况下,只需考虑它关于n的增长率或阶即可。

    例如

    for(i=2;i<=n;++i)

    for(j=2;j<=i-1;++j)

    {

    ++x;

    a[i,j]=x;

    }

    其中++x语句频度为:1+2+3+…+n-2=(n-1)(n-2)/2=(n2-3n+2)/2故算法的时间复杂度可表示为:T(n)=O(n2)

    3. 时间复杂度的计算方法

    时间复杂的推导方法一般如下:

    第一步:用常数1取代运行时间中的所有加法常数。

    第二步:在修改后的运行次数函数中,只保留最高阶项。

    第三步:如果最高阶项存在且不是1,则去除与这个项相乘的常数。

    时间复杂度一般分为以下几种,分别是:

    (1)常数阶 首先顺序结构的时间复杂度。

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    main()

    {

    int sum=0,n=100;

    sum=(1+n)*n/2;

    printf(“%d”,sum);

    }

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    算法的时间复杂度为O(1)。 这个算法的运行次数函数是f(n)=3。根据我们推导的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。

    (2)线性阶 要确定某个算法的阶次,需要确定某个特定语句或某个语句集运行的次数。因此,要分析算法的复杂度,关键就是要分析循环结构的运行情况。

    int i; for(i=0;i

    {

    /*时间复杂度为O(1)的程序步骤序列*/

    }

    (3)对数阶

    int count=1;

    while(count

    { count=count*2; /*时间复杂度为O(1)的程序步骤序列*/}

    由于每次count乘以2之后,就距离n更近了一点。也就是说,有多少个2相乘后大于n,则会退出循环。由2x=n得到x=log2n。所以这个循环的时间复杂度为O(log2n)。

    (4)平方阶

    48304ba5e6f9fe08f3fa1abda7d326ab.png

    inti,j;

    for(i=0;i

    {

    for(j=0;j

    { /*时间复杂度为O(1)的程序步骤序列*/

    }

    }

    循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。间复杂度为O(n2)。

    4. 总结

    本文主要讨论算法的时间复杂度,算法时间复杂度在数据结构中是比较难的问题,通过本文给出的计算时间复杂度的方法,能够比较容易掌握时间复杂的计算。

    展开全文
  • 算法时间复杂度计算方式

    万次阅读 多人点赞 2019-04-09 14:53:00
    算法的正确性评估不在本文范围之内,本文主要讨论从算法时间复杂度特性去评估算法的优劣。】 如何衡量一个算法的好坏呢? 显然,选用的算法应该是正确的(算法的正确性不在此论述)。除此之外,通常有三个方面的...
  • 算法时间复杂度大小顺序

    千次阅读 2020-08-15 11:20:48
    O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
  • 几种常见排序算法时间复杂度

    万次阅读 2020-07-15 15:36:47
    插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是O(n^2)喽。 2、 ...
  • 关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
  • 文章目录前言1、递归算法性能分析公式1.1 时间复杂度计算公式1.2 空间复杂度计算公式1.3 例子1.3.1 暴力算法1.3.2 递归算法1.3.3 优化递归算法总结 前言 根据代码随想录博主整理的 主要是为了记录递归算法如何分析...
  • 算法时间复杂度分析

    千次阅读 2019-03-19 21:02:21
    一、算法复杂度 算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合,简单来说就是解决特定问题求解步骤的描述。对于一个问题,一旦某种算法给定并且是正确的,那么重要的一步,...算法复杂度分为时间复...
  • 为了达到此目的,必须熟悉算法时间复杂度与问题规模之间的关系。 常见的对应关系如下图所示。即若给出了某种问题规模,那么只能设计出对应的时间复杂度的算法,才能不超限。 【参考文献】 ...
  • 详细概述算法时间复杂度(C语言)

    千次阅读 多人点赞 2019-12-01 18:32:43
    其实,在学它之前,自己也会这样想,现在电脑中CPU运行速度这么快且相关的性能也显著提高,为什么还要去学习怎么去提高算法效率,怎么去计算或者表示算法时间复杂度呢?当然,上述的话还不无道理,然而,当你能够去...
  • C++算法篇 算法时间复杂度图解

    千次阅读 多人点赞 2019-12-22 16:00:09
    究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司...... 一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒,内存占用5MB...
  • cpp代码-C/C++ 字符串匹配算法时间复杂度比较
  • 常见的算法时间复杂度计算分析-总结

    千次阅读 多人点赞 2020-03-26 11:14:20
    2. 如果是递归算法,且只进行一次递归调用,有以一种方法是先求出深度depth,求出每一次执行的时间复杂度T ,总的时间复杂度就是depth * T(和用下面的方法原理是一样的。。) 如果递归比较复杂,那么套用递归算法...
  • 算法时间复杂度-对数复杂度

    千次阅读 2020-04-07 22:43:06
    衡量一个算法性能好坏的指标:时间复杂度、空间复杂度 在上位机中,更关注时间复杂度时间复杂度的衡量方法:大O计法 常见的几种时间复杂度:O(n3) O(n2) O(nlogn) O(n) O(log n) O(1) 在分析时间复杂度时,对数...
  • 递归算法时间复杂度分析

    万次阅读 多人点赞 2018-09-17 16:16:59
    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T...
  • 算法时间复杂度实验报告.doc
  • 算法时间复杂度 1.算法时间复杂度定义 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))...
  • 算法时间复杂度分析(1)

    千次阅读 2020-03-23 20:14:28
    复杂度分析简介 常数项不计入复杂度 ...当数据规模小的时候,...但是要注意两部分的n是否相同,n不同时间复杂度由两部分组成: 数据规模 复杂度:O(n) 数据规模每上升10倍,时间增加十倍 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 547,413
精华内容 218,965
关键字:

算法时间复杂度

友情链接: WebSocketDemo.rar