精华内容
下载资源
问答
  • 代码的时间复杂度怎么算
    千次阅读
    2019-09-24 23:28:03

    算法评价:

    时间复杂度和空间复杂度

    时间复杂度:所有语句执行的次数。
    用T(n)来衡量时间复杂度。
    一般不同的输入会有不同的时间复杂度。

    计算方法:先找到循环变量i

    例1

    for(i=1;i<n;i=i*2)
    	std::cout<<i<<std::endl;
    
    1. 确定循环终止条件: i < = n i<=n i<=n
    2. 循环变量的增加方式: i = i ∗ 2 i=i*2 i=i2
    3. 假设执行了t次, i = 2 t i=2^{t} i=2t,代入1
    4. 2 t < = n 2^{t}<=n 2t<=n ==> t < = log ⁡ 2 n t<=\log_2n t<=log2n

    T(n)= log ⁡ 2 n \log_2n log2n= O ( log ⁡ 2 n ) O(\log_2n) O(log2n)

    例2.一算法所需时间由下述递归方程表示,求该算法时间复杂度。
    T ( n ) = { 1 , n = 1 2 T ( n / 2 ) + n , n > 1 T(n)=\begin{cases} 1& ,n=1\\ 2T(n/2)+n& ,n>1\\ \end{cases} T(n)={12T(n/2)+n,n=1,n>1
    n是问题规模,为简单起见n为2的整数次幂。
    解:
    令 n = 2 k , 则 k = 0 时 , T ( 2 k ) = 1 ; 令n=2^k,则k=0时,T(2^k)=1; n=2k,k=0T(2k)=1;

    k > 0 时 , T ( 2 k ) = 2 T ( 2 k − 1 ) + 2 k , k>0时,T(2^k)=2T(2^{k-1})+2^k, k>0T(2k)=2T(2k1)+2k,

    T ( 2 k ) 2 k = T ( 2 k − 1 ) 2 k − 1 + 1 , \frac{T(2^k)}{2^k}=\frac{T(2^{k-1})}{2^{k-1}}+1, 2kT(2k)=2k1T(2k1)+1,

    令 y k = T ( 2 k ) 2 k = > y k = y k − 1 + 1 , 又 y 0 = 1 , 令y_k=\frac{T(2^k)}{2^k}=>y_k=y_{k-1}+1,又y_0=1, yk=2kT(2k)=>yk=yk1+1,y0=1,

    y k = k + 1 , 得 T ( 2 k ) = 2 k ( k + 1 ) y_k=k+1,得T(2^k)=2^k(k+1) yk=k+1,T(2k)=2k(k+1)

    T ( n ) = n ( log ⁡ 2 n + 1 ) = n log ⁡ 2 n + n T(n)=n(\log_2n+1)=n\log_2n+n T(n)=n(log2n+1)=nlog2n+n

    得时间复杂度级别为 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)

    更多相关内容
  • 代码时间复杂度计算

    千次阅读 2020-08-26 21:42:28
    时间复杂度公示: 下面分析一段代码: 2、3、4行每一行都需要1个单位的执行时间,5、6行循环了N边,需要2N个单位时间,7、8行执行了n^2遍,所以一共需要执行时间:(2N ^2 + 2N + 3 )*单位时间。 我们用T(n) 表示...

    时间复杂度公示:
    在这里插入图片描述
    下面分析一段代码:
    在这里插入图片描述
    2、3、4行每一行都需要1个单位的执行时间,5、6行循环了N边,需要2N个单位时间,7、8行执行了n^2遍,所以一共需要执行时间:(2N ^2 + 2N + 3 )*单位时间。
    我们用T(n) 表示,O表示T(n)与f(n)成正比(单位时间),所以表达式可以写成:T(n) = O(2N ^2 + 2N + 3 ) ,这就是大O时间复杂度表示法,由于N无穷大,所以只需要表示最大量级即可,即:T(n) = O(N ^2 )

    时间复杂度分析:

    1、只关注循环执行次数最多的一段代码;
    2、加法法则:总复杂度等于量级最大的那段代码的复杂度;
    例如:时间复杂度:T(n) = O(N+N ^2 ) = O(N ^2 )
    在这里插入图片描述

    3、乘法法则:嵌套代码的复杂度等于嵌套内外代码的复杂度乘积;
    例如:
    以下算法时间复杂度为:T(n) = O(N X N)=O(N ^2 )
    在这里插入图片描述

    展开全文
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • Source Monitor能够检查函数/方法的圈复杂、代码深度注释率等指标,帮助改进代码的可维护性。
  • js代码-介绍算法时间复杂度
  • 时间复杂度到底怎么 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。 那么我们应该...

    时间复杂度到底怎么算

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

    那么我们应该如何去衡量不同算法之间的优劣呢?

    主要还是从算法所占用的「时间」和「空间」两个维度去考量。

    时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
    空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

    因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

    时间复杂度

    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或「时间频度」。记为T(n)。

    时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称「时间复杂度」。

    这种表示方法我们称为「 大O符号表示法」,又称为渐进符号,是用于描述函数渐进行为的数学符号

    常见的时间复杂度量级有:

    常数阶 O ( 1 ) O(1) O(1)
    线性阶 O ( n ) O(n) O(n)
    平方阶 O ( n 2 ) O(n^2) O(n2)
    立方阶 O ( n 3 ) O(n^3) O(n3)
    对数阶 O ( l o g n ) O(logn) O(logn)
    线性对数阶 O ( n l o g n ) O(nlogn) O(nlogn)
    指数阶 O ( 2 n ) O(2^n) O(2n)

    常数阶 O ( 1 ) O(1) O(1)

    O ( 1 ) O(1) O(1),表示该算法的执行时间(或执行时占用空间)总是为一个常量,不论输入的数据集是大是小,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:
    在这里插入图片描述
    上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用 O ( 1 ) O(1) O(1)来表示它的时间复杂度。

    线性阶 O ( n ) O(n) O(n)

    O ( n ) O(n) O(n),表示一个算法的性能会随着输入数据的大小变化而线性变化,如
    在这里插入图片描述
    这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用 O ( n ) O(n) O(n)来表示它的时间复杂度。

    平方阶 O ( n 2 ) O(n^2) O(n2)

    O ( n ) O(n) O(n) 表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话,算法的性能将会变为立方阶 O ( n 3 ) O(n3) O(n3) O ( n 4 ) O(n4) O(n4) O ( n k ) O(n^k) O(nk)以此类推
    在这里插入图片描述

    指数阶 O ( 2 n ) O(2^n) O(2n)

    O ( 2 n ) O(2^n) O(2n),表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是裴波那契数列的递归计算实现
    在这里插入图片描述

    对数阶 O ( l o g n ) O(logn) O(logn)

    在这里插入图片描述
    上面的代码,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了,直到i不小于n退出。我们试着求解一下,假设循环次数为x,也就是说 2 的 x 次方等于 n,则由2^x=n得出x=logn。因此这个代码的时间复杂度为 O ( l o g n ) O(logn) O(logn)

    线性对数阶 O ( n l o g n ) O(nlogn) O(nlogn)

    线性对数阶$O(nlogn) , 就 是 将 时 间 复 杂 度 为 对 数 阶 ,就是将时间复杂度为对数阶 O(logn) 的 代 码 循 环 n 遍 的 话 , 那 么 它 的 时 间 复 杂 度 就 是 n ∗ O ( l o g N ) , 也 就 是 了 的代码循环n遍的话,那么它的时间复杂度就是 n * O(logN),也就是了 nnO(logN)O(nlogn)$,如下:
    在这里插入图片描述
    除此之外,其实还有平均情况复杂度、最好时间复杂度、最坏时间复杂度。。。一般没有特殊说明的情况下,都是值最坏时间复杂度。

    空间复杂度

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

    一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

    一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。当一个算法的空间复杂度与n成线性比例关系时,可表示为 0 ( n ) 0(n) 0(n),类比时间复杂度。

    空间复杂度比较常用的有:O(1)、O(n)、O(n)

    空间复杂度 O ( 1 ) O(1) O(1)

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)举例:
    在这里插入图片描述
    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    空间复杂度 O ( n ) O(n) O(n)

    在这里插入图片描述
    这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

    复杂度速查表

    图例
    在这里插入图片描述
    大-O 复杂度曲线
    在这里插入图片描述
    抽象数据结构的操作复杂度

    在这里插入图片描述
    数组排序
    在这里插入图片描述
    图操作
    在这里插入图片描述
    堆操作
    在这里插入图片描述

    展开全文
  • 本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度。 渐进时间复杂度 时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个运行时间是...
  • 算法的执行效率,粗略的讲就是算法代码执行的时间,在我们不做精确监控统计,靠观察怎么分析代码执行的时间呢? int cal(int n) { int sum = 0;--------2 int i = 1;--------3 for (; i <= n; ++i) {-------...

    最近练习算法题,又看了极客时间中的《数据结构与算法之美》写的真不错,于是总结一下关于复杂度的知识,代码和图片都是课程里面的。虽然是按课程写的,但是自己写一遍最好,否则看过就忘了。

    数据结构与算法本身解决的是的问题。如何让代码运行的更快,如何更省空间有个重要的标准:复杂度分析

    一、大 O 复杂度表示法

    算法的执行效率,粗略的讲就是算法代码执行的时间,在我们不做精确监控统计,靠观察怎么分析代码执行的时间呢?

    int cal(int n) {
       int sum = 0;--------2
       int i = 1;--------3
       for (; i <= n; ++i) {--------4
         sum = sum + i;--------5
       }
       return sum;
     }

    上面这段代码是计算1到n的累加和,从CPU的角度来看每一行的执行都是:读数据-计算-写数据。尽管每行代码对应的CPU执行时间都不一样,做粗略计算的时候只需要估算,把这个时间看成相同的一个时间:unit_time。

    2,3行代码分别需要1*unit_time,for循环里面的第4,5行需要n*unit_time,得到的结果是2*unit_time+2n*unit_time = (2n+2)*unit_time。得出一个结论:所有代码执行的时间T(n)与每行代码执行的时间unit_time成正比

    按照这个方法看下面一段代码:

    int cal(int n) {
       int sum = 0;--------2
       int i = 1;--------3
       int j = 1;--------4
       for (; i <= n; ++i) {--------5
         j = 1;--------6
         for (; j <= n; ++j) {--------7
           sum = sum +  i * j;--------8
         }
       }
     }

    2,3,4分别行执行了1次总共3*unit_time,5,6行分别执行了n*unit_time,7,8行分别执行了n^2*unit_time,总共是(2n^2+2n+3)*unit_time.尽管不知道*unit_time的具体值,但还是得到那个规律:代码执行的时间T(n)与每行代码执行的次数f(n)成正比

    总结一个公式就是:

    1.  T(n)表示代码执行时间
    2. n是数据规模
    3. f(n)是每行代码执行次数总和
    4. O表示代码执行时间和代码执行总次数成正比

    所以第一段代码的T(n) = O(2n+2),第二段代码的T(n) = O(2n^2+2n+3)这就是时间复杂度(asymptotic time complexity)的表示方法

    而代码规模n很大时就可以忽略掉低阶,常量和系数,最终得到,第一段代码的T(n) = O(n),第二段T(n) = O(n^2)

    二、时间复杂度分析

    1.只关注循环执行次数最对的代码

    就像上面第一段代码,我们只关注for循环的运行次数就可以得出这段代码的时间复杂度是T(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

    1. 第一部分for'循环了100次,时间复杂度是O(1),常数级别的如果有更高阶可以忽略掉,为什么是O(1)下面解释
    2. 第二部分的时间复杂度分别是O(n)
    3. 第三部分的时间复杂度分别是O(n^2)

    很显然最高阶是第三部分,所以这段代码的时间复杂度是O(n^2)

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

    看一段代码

    
    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;
     }

    for循环里面嵌入的方法f(x)的时间复杂度为O(n)外部for循环的复杂度是O(n)那么这段代码的时间复杂度就是O(n*n)=O(n^2)。其实还是跟上面分析的一样是两个否循环的嵌套跟2中那个最高阶的一样。

    三、常见的时间复杂度实例

    上面这些可以分两类,多项式量级非多项式量级,其中费多项式量级只有划黄色下划线那两个。非多项式量级的算法问题叫作 NP(Non-Deterministic Polynomial,非确定多项式)问题。

    按我们的数学知识,非多项式量级的时间复杂度会随数据规模n的增大而急剧增大,求解问题的执行时间会无线增长,所以非多项式量级的算法其实效率非常低。所以不多去分析了,只分析多项式量级算法。

    1.O(1)

    看段代码

     int i = 8;
     int j = 6;
     int sum = i + j;

    这段代码的时间复杂度并不是O(3)而是O(1),只要代码的运行时间不随n的增大而增长我们都记作O(1),只要不存在递归和循环,再多行代码的时间复杂度都是O(1)

    2. 对数阶O(logn)、O(nlogn)

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

    不难看出这段代码的第三行的阶数最高,i的取值是个等比数列

    x=\log_{2}n如果把2换成3就有\log_{3}n其实不管底是2,3还是10时间复杂度都可以记为O(logn)因为\log_{3}n=(C * \log_{2}n其中C = \log_{3}2是个常数可以忽略,对数阶时间复杂度表示的时候可以省略调对数的底,统一写成O(logn)。理解了这个O(nlogn)其实就不难理解了,就是一个嵌套的乘法法则,一个循环嵌套一个时间复杂度为O(logn)的代码。比如归并排序和快速排序的时间复杂度都是O(nlogn)

    3. O(m+n)、O(m*n)

    代码的时间复杂度由两种数据的规模来决定

    
    int cal(int m, int n) {
      int sum_1 = 0;
      int i = 1;
      for (; i < m; ++i) {
        sum_1 = sum_1 + i;
      }
    
      int sum_2 = 0;
      int j = 1;
      for (; j < n; ++j) {
        sum_2 = sum_2 + j;
      }
    
      return sum_1 + sum_2;
    }

    像这种我们无法预估m和n的量级谁的比较大,所以无法用加法法则忽略掉一个,所以表示为O(m+n),但乘法法则依然有效所以可以有O(m * n)

    四、空间复杂度

    空间复杂度的全称是渐进空间复杂度(asymptotic space complexity),表示的是算法的存储空间跟数据规模的增长关系。看代码:

    void print(int n) {
      int i = 0;
      int[] a = new int[n];
      for (i; i <n; ++i) {
        a[i] = i * i;
      }
    
      for (i = n-1; i >= 0; --i) {
        print out a[i]
      }
    }

    代码中申请了一个长度为n的数组,其他地方没有占用到更多空间,所以空间复杂度就是O(n),常见的空间复杂度就是 O(1)、O(n)、O(n2 ),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。

     

    展开全文
  • 时间复杂度

    2021-01-06 21:18:57
    算法分析神器—时间复杂度 一套图 搞懂“时间复杂度” 目录 一、代码消耗的的时间单位分析 二、什么是时间复杂度? 三、计算时间复杂度? 一、得出运行时间的函数  二、对函数进行简化  四、时间复杂度排行 五、...
  • 主要介绍了科学知识:时间复杂度计算方法,本文介绍了问题的定义、时间复杂度计算步骤、时间复杂度计算规则等内容,需要的朋友可以参考下
  • 今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的,你可能会看到这么一串东西 T...
  • 时间复杂度怎么详解

    千次阅读 2020-03-30 16:10:48
    时间复杂度怎么详解 我们假设计算机运行一行基础代码需要执行一次运算。 int aFunc(void) { printf("Hello, World!\n"); // 需要执行 1 次 return 0; // 需要执行 1 次 } 那么上面这个方法需要执行 2 次运算 ...
  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 因此,评价一个算法的效率主要是看它的时间...
  • 时间复杂度与空间复杂度该怎么?这里一站式搞定!
  • 样本熵计算时间序列的复杂度,熵值高,则复杂度高,熵值低,复杂度低。
  • 不会有人还不知道这些常见代码时间复杂度

    多人点赞 热门讨论 2022-04-22 23:23:13
    列举一些常见的代码时间复杂度的计算
  • 时间复杂度 foriinrange(n): print('Hello world') # O(n) for i in range(n): for j in range(n): # O(n^2) i=1 while(i<N): i=i*2 # O(logN) forjinrange(n): i=1 while(i<N): i=i*2 # O(nlogN) ...
  • 时间复杂度如何计算

    千次阅读 2021-05-04 16:16:03
      时间复杂度用于描述一个算法的运行时间消耗。刷题(leetcode等)也会有部分题要求写出一些进阶解法。 一、简介 1、时间频度T(n)   一个算法执行所耗费的时间,从理论上是不能出来的,必须上机运行测试才能...
  • 评估算法的时间复杂度的技巧小结 这篇文章献给澳门理工学院一起努力的同学们,祝大家早日摆脱算法学习的苦海,找到一叶扁舟。 什么是时间复杂度 众所周知,程序运行的时间长短跟硬件和算法都有关系。当人们想要专注...
  • 时间复杂度是个神秘而又常见的东西,它常常困扰着...此时,一共要循环n次,所以时间复杂度为cN(c是一个常数),其结果就是O(N),显然O(N)就是这个代码时间复杂度。 再列举一个: int sum=0; for(int i=0;i<
  • B 先引入一段代码:1 int cal(intn) {2 int ret = 0;3 int i = 1;4 for (; i < n; ++i) {5 ret = ret +f(i);6 }7 }89 int f(intn) {10 int sum = 0;11 int i = 1;12 for (; i < n; ++i) {13 ...
  • cpp代码-C/C++ 字符串匹配算法时间复杂度比较
  • 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3)复制代码 代码如下://二分查找O(log2n)function erfen($a,$l,$h,$f){ if($l >$h){ ...
  • 所谓的代码复杂度,就是”快“和”省“的问题,快就是代码算法运行的时间短,省就是代码算法使用的内存少,也就是说,衡量代码执行效率,主要有两个维度,时间、空间复杂度大 O 复杂度表示法 如何在...
  • Java~时间复杂度和空间复杂度详解

    千次阅读 2022-03-12 21:46:21
    时间复杂度 常见时间复杂度计算举例 空间复杂度 常见空间复杂度计算举例 算法效率 如何去衡量一个算法的好坏? 通常我们从时间效率和空间效率两个方面去分析算法的好坏。时间效率即时间复杂度,空间效率被...
  • 时间复杂度计算专题

    千次阅读 2022-02-02 16:41:07
    时间复杂度分析、计算 时间复杂度的速度
  • 代码复杂度分析

    千次阅读 2020-12-02 13:48:02
    代码执行时间随数据规模增长的变化趋势, 也叫作渐进时间复杂度,简称时间复杂度。T(n) = O(f(n)) (1) 我们在分析一个算法、一段代码时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 528,771
精华内容 211,508
关键字:

代码的时间复杂度怎么算