精华内容
下载资源
问答
  • 2019-08-14 11:20:27
    1. 时间复杂度简介:
    • 相信大多数人判断一个算法的好坏就是比较算法的执行时间,即经过多长的时间可以运算出结果。其实这并不是正确的。如果对于解决一个问题有2种算法,算法1的执行时间小于算法2,这并不能代表算法1优于算法2。假设执行算法1的计算机性能和环境都低于执行算法2的计算机的性能和环境,那么算法1可能执行的时间会更长。所以可以看出仅仅根据执行时间来衡量算法的优劣不一定是正确的。

    • 算法的衡量标准应该是以时间复杂度来进行衡量。 时间复杂度:就是运算所经历的步骤。

    • 用比较官方的话说就是(摘自百度百科):计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    1. 时间复杂度的分类:
    • 最优时间复杂度:完成运算最少需要多少步骤。(最乐观的情况,我们一般不考虑)
    • 最坏时间复杂度:完成运算最多需要多少步骤。(在实际中,都是关注最坏时间复杂度。)
    • 平均时间复杂度:完成运算平均需要多少步骤。(平均时间复杂度的意义也不大)

    3.时间复杂度的几条基本计算规则:

    • 基本操作,即只有常数项,认为其时间复杂度为O(1)
    • 顺序结构,时间复杂度按加法进行计算
    • 循环结构,时间复杂度按乘法进行计算
    • 分支结构,时间复杂度取最大值
    • 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    • 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    更多相关内容
  • 衡量算法效率最简单的一个办法就是把算法变成一个程序,然后再机器上执行,然后计时,这就是事后统计法。 这样显然有一些缺点: 1.必须到机器上去计算,而且这个计算不只是一次,我们要多组数据对其进行重复的运算...

    一、衡量算法效率的方法(通常有两种)
    1.事后统计法
    衡量算法效率最简单的一个办法就是把算法变成一个程序,然后再机器上执行,然后计时,这就是事后统计法。
    这样显然有一些缺点:
    (1)必须到机器上去计算,而且这个计算不只是一次,我们要用多组数据对其进行重复的运算,然后得到一个统计的结果,那么你要算上机器的时间。
    (2)肯定会有一些其他因素掩盖算法的本质。

    2.事前分析估算法
    通常比较算法好坏,都是在设计算法的时候就应该知道它的效率,这就是事前分析估算法。

    说明: 要比较两个算法,实际上在设计的时候就做着工作来衡量它们的效率,因此更常用的方法是事前分析估算法。

    二、怎么样估算算法的执行时间
    【与算法执行时间相关的因素】
    1.算法选用的策略
    不同的策略选用的算法是不同的,它的执行时间也是不同的。
    2.问题的规模
    问题的规模不一样,算法的执行时间当然不一样。
    例如:两个矩阵相乘,是10×10的,还是10000×10000的,同样一个算法,执行的时间确实不同的。
    3.编写程序的语言
    使用高级语言编写的程序比汇编语言编写的程序的执行时间要长。
    4.编译程序产生的机器代码的质量
    对于同一种高级语言,使用的编译器不同,编译出来的机器代码的质量也会不同。计算机最终执行的是机器代码,机器代码质量不同,算法变成程序后的执行时间也就不同。
    5.计算机执行指令的速度
    机器的速度不一样,执行的时间也是不一样的 。
    例如:一个大型机和一个小型机显然是不一样的。

    说明: 后面的三个因素是与计算机的硬件和软件相关的,跟我们设计算法的时候是无关的,所以在设计算法的时候就不再考虑这三个因素。所以,我们考虑算法执行的时间,取决于算法选用的策略和问题的规模,也就是说,一个算法的执行时间是问题规模的的一个函数

    三、(渐进)时间复杂度
    假如,随着问题规模n的增长,算法执行时间的增长率和 f ( n ) f(n) f(n)的增长率相同,则可记作: T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n)),称 T ( n ) T(n) T(n)为算法的(渐进)时间复杂度。
    T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))表明:算法的执行时间 T ( n ) T(n) T(n),它随着问题规模增大而增大的函数的趋势是和 f ( n ) f(n) f(n)这个函数的趋势是相同的,我们称算法的时间和 f ( n ) f(n) f(n)这个函数是成正比的,或者说,这个算法的时间是和 f ( n ) f(n) f(n)这样一个函数的数量级的。

    四、如何估算算法的时间复杂度
    任何一个算法都是由控制结构和若干个原操作构成的,这里的原操作本来指的是计算机执行的基本指令,但是当我们用伪码语言或者程序语言描述算法的时候,就将固有数据类型的操作看做是原操作,即算法 = 控制结构 + 原操作(固有数据类型的操作)
    时间复杂度考虑的是: 随着问题规模n的增长而增长,时间复杂度是一种趋势。一个算法中有很多的原操作,既然我们考虑的是变化的趋势,那么就不必考虑所有的原操作,而只需要在所有的原操作中选取一种所谓基本操作的原操作就行了。这个基本操作的原操作,对于研究的问题来说,它是在所有的原操作中起决定作用的,那么就以该基本操作在算法中重复执行的次数作为算法执行时间的衡量准则
    说明:算法的执行时间 = ∑原操作(i)的执行次数 × 原操作(i)的执行时间,其中,原操作(i)的执行时间,对于不同的算法来说,它都是一个定值。因此,在估计算法的时候,往往都会把它忽略掉,也就是说,算法的执行时间与原操作的执行次数之和成正比。

    例一、两矩阵相乘

    for (i = 1; i <= n; i++)
    		for (j = 1; j <= n; j++) 
    		{
    			c[i][j] = 0;
    			for (k = 1; k <= n; k++)
    				c[i][j] += a[i, k] * b[k][j];
    		}
    

    这个算法的控制结构是一个三重循环,这里的原操作有赋值、有相加、有相乘。显然,乘法操作是这个算法的基本操作,那么可以用乘法操作执行的次数作为该算法时间复杂度的衡量标准。乘法操作在这个三重循环之内,外循环n次,第二重n次,第三重n次,因此这个乘法操作执行的次数为n3,整个算法的执行时间与n3成正比,则这个算法的时间复杂度为: O O O(n3)。

    例二、选择排序

    void select_sort(int a[], int n)
    	{
    		//将a中整数序列重新排列成自小到大有序的整数序列
    		for (i = 0; i < n - 1; i++)
    		{
    			j = i;
    			for (k = i + 1; k < n; k++)
    				if (a[k] < a[j]) j = k;
    			if(j!=i) a[j]←→a[j]
    		}
    	}//选择排序
    

    这个算法的控制结构是两重循环,原操作有赋值,有比较,有交换。显然,基本操作取比较操作。比较操作在两重循环以内,外层循环n次(实际上是n-1次,但是为了方便,可记作n次),内层循环的次数随着i的变化而变化,依次为n-1,n-2,…,1,总次数为等差数列之和,等于 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n1),即 1 2 n 2 − 1 2 n \frac{1}{2}{n^2}-\frac{1}{2}{n} 21n221n。所以,算法的执行时间与 1 2 n 2 − 1 2 n \frac{1}{2}{n^2}-\frac{1}{2}{n} 21n221n成正比,当然与n2成正比,时间复杂度为 O O O(n2)。

    上面两个例子有两个共同的特点:
    1、一般情况下,算法的基本操作都是在最深层的循环语句中。假如称语句的执行次数为语句的频度,那么在估算算法的时候也可以计算最深层循环中语句的频度,以这个语句频度的函数作为该算法的时间复杂度。
    2、算法的效率与输入数据无关。它只是问题规模的函数,无论输入的数据是什么样的,按问题规模的大小,每一步操作都需要进行。但有的算法不是这样的。

    例三、冒泡排序

    void bubble_sort(int a[], n)
    {
    	//将a中整数序列重新排列成从小到大的有序的整数序列
    	for (i = n - 1, change = true; i > = 1 && change; i--)
    	{
    		change = false;
    		for (j = 0; j < i; j++)
    		{
    			if (a[j] > a[j + 1])
    			{
    				a[j]←→ a[j + 1];
    				change = ture;
    			}
    		}
    	}
    }//bubble_sort
    

    外循环次数取决于 i i i和change,如果一开始的整数序列为[8,7,6,5,4,3,2,1],显然,这个外循环需要进行n-1次;而一开始的整数序列为[1,2,3,4,5,6,7,8,],那么这个外循环只进行1次。分别对应的是最坏的情况和最好的情况,而基本操作比较操作,分别为 1 2 n 2 − 1 2 n \frac{1}{2}{n^2}-\frac{1}{2}{n} 21n221n次和n-1次。这时,算法的效率不仅与问题规模n有关,还与输入数据的取值有关。而时间复杂度通常取最坏的情况 O O O(n2)。

    说明:在有的时候,也可以考虑平均的时间复杂度,所谓平均的时间复杂度是在统计概率的情况下。比如,初始的序列是随机的,也就是出现任何情况的概率都是相同的,这时可以取最好情况下和最坏情况下的平均作为它的平均时间复杂度。对于冒泡排序来说,它的平均时间复杂度仍为 O O O(n2)。

    五、算法的存储空间需求
    与算法的时间复杂度类似,对应讨论的是算法的(渐进)空间复杂度。
    算法的空间复杂度: S ( n ) = O ( g ( n ) ) S(n)=O(g(n)) S(n)=O(g(n))表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。

    算法的存储量包括:
    1、输入数据所占的空间
    2、程序本身所占的空间
    3、辅助变量所占的空间

    说明:任何算法写成程序后,本身都会占有一定的空间,不同的算法占有的空间可能会不同,但是这个差距是细微的,一般情况下,可以不考虑。若输入数据所占空间只取决于问题本身,则只需要分析除输入和程序之外的辅助变量所占的额外空间
    若所需的额外空间相对于输入数据量来说是一个常数,则称此算法为原地工作
    若所需的额外空间依赖于特定的输入,则通常按最坏的情况考虑。

    展开全文
  • 我们假定计算机执行算法一个基本操作的时间是固定的一个时间单位,那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言,确切的单位时间是不同的,但是对于算法进行多少个基本操作(即花费...

    运行时间衡量

    实现算法程序的执行时间可以反应出算法的效率,但是单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的!

    时间复杂度与“大O标记法”

    我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位,那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言,确切的单位时间是不同的,但是对于算法进行多少个基本操作(即花费多少时间单位)在规模数量级上却是相同的,由此可以忽略机器环境的影响而客观的反应算法的时间效率。

    对于算法的时间效率,我们可以用“大O标记法”来表示。

    **“大O记法”:**对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。

    **时间复杂度:**假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)

    如何理解“大O记法”

    对于算法进行特别具体的细致分析虽然很好,但在实践中的实际价值有限。对于算法的时间性质和空间性质,最重要的是其数量级和趋势,这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如,可以认为3n2和100n2属于同一个量级,如果两个算法处理同样规模实例的代价分别为这两个函数,就认为它们的效率“差不多”,都为n2级。

    最坏时间复杂度

    分析算法时,存在几种可能的考虑:

    算法完成工作最少需要多少基本操作,即最优时间复杂度
    算法完成工作最多需要多少基本操作,即最坏时间复杂度
    算法完成工作平均需要多少基本操作,即平均时间复杂度
    对于最优时间复杂度,其价值不大,因为它没有提供什么有用信息,其反映的只是最乐观最理想的情况,没有参考价值。

    对于最坏时间复杂度,提供了一种保证,表明算法在此种程度的基本操作中一定能完成工作。

    对于平均时间复杂度,是对算法的一个全面评价,因此它完整全面的反映了这个算法的性质。但另一方面,这种衡量并没有保证,不是每个计算都能在这个基本操作内完成。而且,对于平均情况的计算,也会因为应用算法的实例分布可能并不均匀而难以计算。

    因此,我们主要关注算法的最坏情况,亦即最坏时间复杂度。

    时间复杂度的几条基本计算规则

    1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
    2. 顺序结构,时间复杂度按加法进行计算
    3. 循环结构,时间复杂度按乘法进行计算
    4. 分支结构,时间复杂度取最大值
    5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    展开全文
  • 还在头疼时间复杂度如何计算?来看下本文,彻底学会时间复杂度问题的求解。

    ​ 一直都说算法很重要,写出一个好算法不容易。那么有怎么样来评价一个算法的好坏呢?算法的评价指标主要有四个:正确性、可读性、健壮性、高效率与低存储量。其中的高效率,一般是通过时间复杂度来进行衡量。但时间复杂度却是困扰众多学子的一大”难题“,许多刚学数据结构的同学都被难到了。本文,我们就一起来学习下,通过几个案例,来彻底理解时间复杂度。

    1.为什么是时间复杂度

    ​ 算法的执行时间需要通过依据该算法编写的程序在计算机上运行时所消耗的时间来度量的。而度量一个程序的执行时间通常有两种方法。

    1. 事后统计方法:根据算法编写程序,然后在计算机上执行,得到执行时间。
    2. 事前分析估算方法:通过理论分析,在问题求解的规模下,得到”运行工作量“,也就是时间复杂度

    ​ 一个用高级程序语言辨析的程序在计算机上的运行时所耗时间取决于下面五个因素:

    • 依据算法选用何种策略;
    • 问题的求解规模,例如求100以内还是1000以内的素数;
    • 书写程序的语言,对于同一种算法,实现语言的级别越高,执行效率就越低;
    • 编译程序所产生的机器代码的质量;
    • 机器执行指令的速度。

    ​ 显然,同一个算法使用不同的语言实现、用不同的编译程序进行编译、在不同的计算机上运行时,执行的耗时都有差异。这表明使用绝对的时间单位来衡量算法的效率是不合适的。而且使用事后统计方法,还需要先将算法实现,并在计算机上执行,加大了工作难度。

    ​ 撇开这些与计算机硬件、软件有关的因素,可以认为一个特定的算法”运行工作量“的大小,只依赖于问题的规模(通常用整数量n来表示),或者说,他是问题规模的函数。

    ​ 为了便于比较同一问题的不同算法,通常的做法是,从算法中选取一两种对于所研究的问题来说是基本操作的原操作,以改基本操作重复执行的次数作为算法的时间复杂度

    ​ 我们以一个小栗子来简单介绍下,下面是两个N*N矩阵相乘的算法,”乘法“运算是”矩阵相乘问题的基本操作。整个算法的执行时间与该基本操作重复执行的次数n3成正比,记作:
    T ( n ) = O ( n 3 ) T(n) = O(n^3) T(n)=O(n3)

    for(i=1; i<-n; ++i)
      for(j=1; j<=n; ++j){
        c[i][j] = 0;
        for(k=1; k<=n; ++k)
          c[i][j] += a[i][k] * b[k][j]
      }
    

    2.时间复杂度的概念

    ​ 一般情况下,算法中的基本操作执行的次数是问题规模n的某个函数f(n),算法的时间量度记做
    T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))
    他表示随着问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。

    ​ 除了上述之外,还有一个其他的概念,如下所示:

    • 最坏时间复杂度:指在最坏情况下,算法的时间复杂度;
    • 平均时间复杂度:指所有可能输入实例在等概率条件出现的情况下,算法的期望运行时间;
    • 最好时间复杂度:指在最好情况下,算法的时间复杂度。

    ​ 我们以排序问题为例,最坏的情况是指所有的元素都不在指定的位置上,或者说是逆序的;最好情况就是输入的序列本身就是按照要求(升序、降序)有序的;平均情况是考虑所有的输入情况下,平均下来的时间复杂度。

    ​ 一般情况下,我们总是考虑在最坏情况下的时间复杂度,即分析最坏情况以估算算法执行时间的一个上节,保证算法的运行时间不会比它更长。

    ​ 在分析一个程序的时间复杂度是,有以下两条准则:

    1. 加法规则
      T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f ( n ) ) + O ( g ( n ) ) = O ( M a x ( f ( n ) , g ( n ) ) ) T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(Max(f(n), g(n))) T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(Max(f(n),g(n)))

    2. 乘法规则
      T ( n ) = T 1 ( n ) ∗ T 2 ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n)) T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)g(n))

    常见的渐进时间复杂度有:
    O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

    3.空间复杂度

    ​ 空间复杂度,相比于时间复杂度就简答的多了。

    ​ 算法的空间复杂度S(n),定义为该算法所耗费的存储空间,它是问题规模n的函数。记做:
    S ( n ) = O ( g ( n ) ) S(n) = O(g(n)) S(n)=O(g(n))
    ​ 一个程序出了需要存储空间来存放本身所用的指令、常数和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间,若输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外的额外空间,否则应同时考虑输入本身所需的空间(和输入数据的表现形式有关)。

    ​ 若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。如交换两个变量的值,代码需要定义一个临时变量,那么空间复杂度就是O(1),属于原地工作。部分排序算法,就属于此类,如交换排序。

    4.一些例子

    ​ 光说不练,假把式。下面我们来通过一些典型的案例,来一起看下时间复杂度到底是如何计算的。

    void funA(int n) {
      // 循环次数为 n
      for(int i = 0; i < n; i++) {
        //基本运算
        printf("Hello, World!\n");
      }
    }
    

    ​ 上面问题中,基本运算和问题规模n有关,输出语句执行的次数等于i++的次数,因此T(n) = O(n).

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

    ​ 上面问题中,基本运算是i=i*2,设其执行时间为T(n),则2T(n)<=n,T(n) <= log2n = O(log2n).

    void funC(int n) {
      int count=0;
      for(int k=1; k<=n; k*=2)
        for(int j=1; j<=n; j++)
          count++;
    }
    

    ​ 这个问题中有两层循环,需要单独分析。内层循环条件j<=n与外层循环的变量无关,由前两个例子可知,内层循环的时间复杂度为O(n);外层循环条件为k<=n,可知循环次数为2k<=n,即k<=log2n,外层循环的时间复杂度为O(log2n)。根据时间复杂度的乘法规则可知,该程序的时间复杂度T(n) =T1(n) * T2(n) =O(n) * O(log2n) = O(nlog2n)。

    void funD(int n) {
        // 第一部分时间复杂度为 O(log2n)
        int i=1;
        while(i<=n)
          i = i*2;
        // 第二部分时间复杂度为 O(n)
        for(int j = 0; j < n; j++) 
            printf("Hello, World!\n");
    }
    

    ​ 上面问题中,可以看到,两个循环是顺序执行的,根据加法规则可知,总的时间复杂度T(n) =T1(n) + T2(n) =O(n) + O(log2n) = Max(O(n), O(log2n)) = O(n)。当程序段中出现分支结构(if)时,也是相同的,其执行频率最高的为该算法的时间复杂度。

    4.一些练习

    ​ 上面讲了一些基本的例子,下面我们通过一些题目来简单练一练。

    1.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是_________。

    x=2;
    while(x<n/2)
      x=2*x
    

    ​ 在程序中,基本运算为x=2*x,设该语句执行了t次,2t+1>=n/2,t>=log2(n/2) - 1 = log2n - 2,因此时间复杂度为O(log2n).

    2.求整数n(n>=0)阶乘的算法如下,其时间复杂度是_________.

    int fact(int n){
      if(n<=1) return 1;
      return n * fact(n-1);
    }
    

    ​ 本题中,是就n的阶乘的递归问题,不过也没有想象的这么复杂,n!=n*(n-1)…1,共执行n次乘法操作,故T(n) = O(n)。

    3.求斐波那契数列的递归算法如下,其时间复杂度是_________.

    int fibonacci(int n){
      if(n==1 || n=2)
        return 1;
      return fibonacci(n - 1) + fibonacci(n - 2);
    }
    

    ​ 本题中,递归变得稍微复杂了些,由题可知,F(n) = F(n-1) + F(n-2),相求F(n-1)需要求出F(n-2)和F(n-3)的值,这种递归的求F(n)的值,有点类似于二叉树,且可以知道二叉树的高度为n,求F(n)需要的计算量可以约等于于二叉树的节点数,即每个节点都需要计算。这样可以知道T(n) = 1 + 2 + 4 … + 2n-1 = 2n-1,因此O(n) = 2n.

    4.下面算法的时间复杂度为_________.

    void funE(int n){
      int i=0,s=0;
      while(s<n){
        ++i;
        s=s+i;
      }
    }
    

    ​ 由题可以发现,基本操作为++i、s = s+i,且都与循环的结束条件有关,问题似乎是变得复杂了,但是难不倒你。假设循环执行m次结束,则由s1 = 1; s2 = 1+2=3; s3 = 1+2+3=6…;sm = 1+2…+m=m(m+1)/2,则有m(m+1)/2 + K=n,(其中K为起修正作用的常数,可以理解为执行m+1次,sm+1>=n,sm + K=n),求值可得:
    m = − 1 + 8 n + 1 − 8 K 2 m=\frac{-1+\sqrt{8n+1-8K}}2 m=21+8n+18K
    由此可知T(n) = f(n) = − 1 + 8 n + 1 − 8 K 2 \frac{-1+\sqrt{8n+1-8K}}2 21+8n+18K = O( n \sqrt{n} n ),时间复杂度为 O( n \sqrt{n} n )。

    5.总结

    ​ 通过以上分析,我们总结出计算一个算法的时间复杂度的具体步骤如下:

    1. 确定算法中的基本操作以及问题的规模。
    2. 根据基本操作的执行情况计算出规模n的函数f(n),并确定时间复杂为T(n) = O(f(n)中增长最快的项/此项系数).

    ​ 对于时间复杂度求解,许多同学一眼能看出程序的时间复杂度,但是无法将其推到过程规范的表达出来。其实这类问题分为两种形式,其求解思路如下:

    一是循环主体中的变量参与循环条件的判断。此类问题应当找出主体语句中与T(n)成正比的循环变量,将之带入条件中进行计算。例如练习题中的4.1,x*2的次数正是主体语句的执行次数T(n),因此有2t+1>=n/2,最后时间复杂度为O(log2n)。

    ​ 二是循环主体中的变量与循环条件无关。此类问题可采用数学归纳法,或直接累计循环次数;多层循环时从内到外分析,忽略单步语句、条件判断语句,只关注主体语句的执行次数。此类问题有可分为递归和非递归程序。

    • 递归程序一般采用公式进行递推,如例题4.2、4.3
    • 非递归程序比较简单,可以直接累计次数。

    ​ 又到了分隔线以下,本文到此就结束了,本文内容全部都是由博主自己进行整理并结合自身的理解进行总结,如果有什么错误,还请批评指正。

    ​ 本专栏为数据结构知识,喜欢的话可以持续关注,如果本文对你有所帮助,还请还请点赞、评论加关注

    ​ 有任何疑问,可以评论区留言。

    展开全文
  • 算法效率

    2021-01-07 15:41:12
    算法效率(Efficientcy)的分析,指的是算法求解的一个问题所需要的时间和空间 时间资源和空间资源 如何衡量时间资源?建例一个客观的计算模型 计算模型(Turing 机、以及RAM(随机存储器))等 算法时间资源的估算 ...
  • 大家先思考一个问题:当你面对一道编程题或者需要实现某个功能...同一个问题,好的算法2秒就搞定,而效率低的算法半天运行不出来甚至直接死机。 那怎样的代码才算是效率高的代码呢? 首先,效率高≠运行时间短。算法
  • 算法效率衡量

    千次阅读 2017-11-18 07:58:26
    执行时间反应算法效率假设对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行时间进行了测算,发现两段程序执行时间相差悬殊,由此我们可以得出结论:实现算法程序的执行时间可以反应出...
  • 一、排序算法的介绍 简介 排序也称排序算法 (Sort ...1、度量一个程序(算法)执行时间的两种方法 1)事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序
  • 文章目录为什么需要复杂度分析?1. 测试结果非常依赖测试环境2.测试结果受数据规模的影响很大大O复杂度表示法时间复杂度... 必须明确一个概念:常量级时间复杂度的一种表示方法O(1)2.对数阶时间复杂度 O(logn)、O(n...
  • 复杂度分析(上):如何分析、统计算法执行效率和资源消耗
  • 如何去评估一个算法时间复杂度?

    多人点赞 热门讨论 2022-03-27 15:13:22
    两种算法的比较 你知道数学家高斯那个关于1+2+3+…+100的故事吗? 高斯7岁那年开始上学。10岁的时候,位老师想治治班上的淘气学生,他出了一道数学题,让学生从1+2+3……一直加到100为止。他想这道题足够...
  • 算法效率的度量方法

    千次阅读 2021-01-02 01:11:37
    这里的效率大都指算法执行时间,那么我们如何度量一个算法执行时间呢? 事后统计方法 这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的...
  • 算法效率衡量 时间复杂度与“大O记法” 最坏时间复杂度 五:时间复杂度的几条基本计算规则 六:算法分析 第次尝试的算法核心部分 第二次尝试的算法核心部分 七:常见时间复杂度 常见时间复杂度之间的...
  • 当我们学习编程语言到达一定程度之后,就会开始注重代码的效率,这时候就会开始研究算法这么东西,算法顾名思义就是计算方法,就好比你做一道数学题,有简单的办法也有麻烦的办法,但是简单的办法不好理解,在代码...
  • 算法效率的度量通过时间复杂度和空间复杂度来衡量。 一般考察时间复杂度的内容偏多,空间复杂度了解就行。 1.时间复杂度 语句的频度是指一个语句在算法中被重复执行的次数。 时间复杂度是指执行算法所需要的计算...
  • 时间复杂度是衡量算法执行效率种标准。但是,时间复杂度并不能跟性能划等号。在真实的软件开发中,即便在不降低时间复杂度的情况下,也可以通过一些优化手段,提升代码的执行效率。毕竟,对于实际的软件开发来说...
  • 算法效率衡量 在计算机领域,算法的衡量有两个重要标准:时间复杂度和空间复杂度 时间复杂度 对于时间复杂度,得先理解一下程序的基本操作执行次数 基本操作执行次数 举几个例子: 假如你有一个10cm的面包,你吃1...
  • 1.衡量一个算法好坏的标准在于其算法效率高,算法效率分为时间复杂度和空间复杂度,时间复杂度主要衡量一个算法的运行速度,空间复杂度主要衡量一个算法所需要的额外空间。一个算法好应该时间复杂度最低,空间复杂度...
  • 时间复杂度和空间复杂度是衡量算法的重要指标,对于排序算法特定算法,这篇文章整理了一些常见的基础性的指标,后续将以此为基础进行进一步的解释。
  • 假设每行代码的执行时间为unit_time T(n):代码的总执行时间 f(n):每行代码执行的次数总和 O:表示代码的执行时间T(n)与f(n)表达式成正比 T(n)=O(f(n)) 大 O 时间复杂度实际上并不具体表示代码真正的执行时间,...
  • 、首先好算法衡量标准是 正确性:指算法能够满足具体问题的需求,程序运行正常,无语法错误,能过通过典型的软件测试,达到预期需求规格。 易读性:指算法遵循标识符命名规则,简洁,易懂,注释语句恰当、适量...
  • 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要 的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机 行业的迅速发展,计算机的...
  • 但对于大多数普通用户来说,可以从以下4指标来大体评价计算机的性能:1、CPU的运算速度运算速度是衡量计算机性能的项重要指标。通常所说的计算机运算速度(平均运算速度),是指每秒钟所能执行的指令条数,一般...
  • “根据系统测试发现缺陷数来衡量测试人员的系统测试效率,测试执行效率”,这种方法是很片面的。它的优点是便于统计和分析,缺点是只通过一个方面考核了测试效率等,漏掉了很多其他因素。那么该如何衡量测试人员的...
  • 算法效率衡量 执行时间反应算法效率 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行时间进行了测算,发现两段程序执行时间相差悬殊(214.583347秒相比于0.182897秒),由此我们...
  • 计算机执行效率衡量一个算法的执行所需要时间(一条指令/语句执行次数)和空间(存储单元数)的,被称为算法时间复杂性和空间复杂性。对于同一个问题,可能有不同的算法,这些算法可能有不同的时间复杂性。算法...
  • 优化代码第步——理解复杂度
  • 目录 1.衡量算法的指标 2.算法时间复杂度 2.1 时间复杂度与“大O记法” 2.2 最坏时间复杂度 2.3时间复杂度的几条基本计算规则 ... 同一个问题可以不同的算法解决,而一个算法的优劣将影...
  • 算法效率衡量

    千次阅读 2018-01-21 14:30:32
    算法效率衡量 先来看一道题: 如果 a+b+c=1000,且 a^2+b^2=c^2(a,b,c 为自然数),如何求出所有a、b、c可能的组合? 执行时间反应算法效率 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,...
  • 如何衡量一个算法的优劣?

    万次阅读 2019-04-24 14:40:15
    时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要 的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机 行业的迅速发展,计算机的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 51,511
精华内容 20,604
关键字:

一个算法的执行时间效率用什么衡量