精华内容
下载资源
问答
  • 算法效率衡量算法效率衡量执行时间反应算法效率单靠时间值绝对可信吗?时间复杂度与“大O记法”如何理解“大O记法”最坏时间复杂度时间复杂度的几条基本计算规则 1.4. 算法效率衡量 算法效率衡量 执行时间反应算法...

    1.4. 算法效率衡量

    在这里插入图片描述

    算法效率衡量

    执行时间反应算法效率

    对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以得出结论:实现算法程序的执行时间可以反应出算法的效率,即算法的优劣。

    单靠时间值绝对可信吗?

    假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中,情况会如何?很可能运行的时间并不会比在我们的电脑中运行算法一的214.583347秒快多少。

    单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的!

    程序的运行离不开计算机环境(包括硬件和操作系统),这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢?

    时间复杂度与“大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. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    展开全文
  • 算法效率衡量标准(时间复杂度)

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

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

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

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

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

    • 基本操作,即只有常数项,认为其时间复杂度为O(1)
    • 顺序结构,时间复杂度按加法进行计算
    • 循环结构,时间复杂度按乘法进行计算
    • 分支结构,时间复杂度取最大值
    • 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    • 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    展开全文
  • 算法效率衡量

    2018-12-01 22:59:47
    并且一个算法花费的时间算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 时间复杂度与“大O记法” 上面提到的时间频度T(n...

    时间频度

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

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

    上面提到的时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有T(n)<=c*g(n),就说函数g是T(n)函数的一个渐近函数(忽略常数),记为T(n)=O(g(n)),它称为算法的渐进时间复杂度,简称时间复杂度。这种用O( )来体现算法时间复杂度的记法,我们称之为大O表示法。

    大O表示法实际就是去掉T(n)函数的最高阶项系数、低阶项和常数项,只保留最高阶项。如T(n)函数为5n3 + 3n + 5,使用大O表示法则时间复杂度为O(n3)。

    如何理解“大O记法”

    对于算法的效率衡量,最重要的是其数量级和趋势,这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如,可以认为3n2和100n2属于同一个量级,如果两个算法处理同样规模实例的代价分别为这两个函数,就认为它们的效率“差不多”,都为n2级。

    时间复杂度的分类

    时间复杂度根据操作的多少分为如下三种:

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

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

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

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

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

    基本操作,即只有常数项,认为其时间复杂度为O(1),
    顺序结构,时间复杂度按加法进行计算
    循环结构,时间复杂度按乘法进行计算
    分支结构,时间复杂度取最大值
    判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

    空间复杂度

    1. 空间复杂度的概念
      类似于时间复杂度的讨论,一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
    2. 空间复杂度和时间复杂度的关系
      对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。大部分时间我们在完成一个程序时采用空间换时间的策略
      算法的时间复杂度和空间复杂度合称为算法的复杂度。
    展开全文
  • 算法效率衡量

    千次阅读 2017-11-18 07:58:26
    执行时间反应算法效率假设对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行时间进行了测算,发现两段程序执行时间相差悬殊,由此我们可以得出结论:实现算法程序的执行时间可以反应出...

    执行时间反应算法效率

    假设对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊,由此我们可以得出结论:实现算法程序的执行时间可以反应出算法的效率,即算法的优劣。
    单靠时间值绝对可信吗?

    假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中,情况会如何?很可能运行的时间并不会比在我们的电脑中运行算法一快多少。

    单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的!

    程序的运行离不开计算机环境(包括硬件和操作系统),这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢?
    时间复杂度与大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级。

    最坏时间复杂度

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

    算法完成工作最少需要多少基本操作,即最优时间复杂度
    算法完成工作最多需要多少基本操作,即最坏时间复杂度
    算法完成工作平均需要多少基本操作,即平均时间复杂度
    

    对于最优时间复杂度,其价值不大,因为它没有提供什么有用信息,其反映的只是最乐观最理想的情况,没有参考价值。

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

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

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

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

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

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

    2019-09-26 16:02:24
    算法效率衡量 执行时间反应算法效率 对于上次的例子,同一问题,给出了两种解决算法,在两种算法的实现中,对程序执行时间进行了测算,发现两段程序执行时间相差悬殊(214.583347秒相比于0.182897秒),由此...
  • 算法效率衡量 时间复杂度与“大O记法” 最坏时间复杂度 五:时间复杂度的几条基本计算规则 六:算法分析 第次尝试的算法核心部分 第二次尝试的算法核心部分 七:常见时间复杂度 常见时间复杂度之间的...
  • 算法效率衡量 执行时间反应算法效率 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行时间进行了测算,发现两段程序执行时间相差悬殊(214.583347秒相比于0.182897秒),由此我们...
  • 衡量算法效率

    2015-08-25 15:44:24
    (1)测量执行时间:Java中使用System.currentTimeMillis()获得毫秒数,在需要测试...(2)指令计数:对一个算法的实现代码计算执行指令次数; (3)测量内存使用率:算法中包含的对象和引用数目,其越多则内存越高。
  • 计算机执行效率衡量一个算法的执行所需要时间(一条指令/语句执行次数)和空间(存储单元数)的,被称为算法时间复杂性和空间复杂性。对于同一个问题,可能有不同的算法,这些算法可能有不同的时间复杂性。算法...
  • 大家先思考一个问题:当你面对一道编程题或者需要实现某个功能...同一个问题,好的算法2秒就搞定,而效率低的算法半天运行不出来甚至直接死机。 那怎样的代码才算是效率高的代码呢? 首先,效率高≠运行时间短。算法
  • 如何衡量一个算法的好坏

    千次阅读 2019-06-24 22:28:06
    我有朋友有算法强迫症,每次看到别人写的算法,就有上去改的冲动,不然就会偏头疼,主要症结在于他认为别人写的算法不好,但是什么算法可以评判为好,什么样的算法可以评判为不好?最近为了治愈他,我特地写了...
  • 如何衡量一个算法的优劣?

    千次阅读 2019-04-24 14:40:15
    时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要 的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机 行业的迅速发展,计算机的...
  • 目录 1.衡量算法的指标 2.算法时间复杂度 2.1 时间复杂度与“大O记法” 2.2 最坏时间复杂度 2.3时间复杂度的几条基本计算规则 ... 同一个问题可以不同的算法解决,而一个算法的优劣将影...
  • 文章目录数据结构-算法-时间复杂度算法特性好算法的标准时间复杂度算法的控制结构算法执行时间T(n)转[O(n)时间复杂度]习题 算法特性 有穷:步骤有穷、时间有限 确定:语句无二义 可行:可运行可实现 输入:输入...
  • 假设每行代码的执行时间为unit_time T(n):代码的总执行时间 f(n):每行代码执行的次数总和 O:表示代码的执行时间T(n)与f(n)表达式成正比 T(n)=O(f(n)) 大 O 时间复杂度实际上并不具体表示代码真正的执行时间,...
  • 文章目录为什么需要复杂度分析?1. 测试结果非常依赖测试环境2.测试结果受数据规模的影响很大大O复杂度表示法时间复杂度... 必须明确一个概念:常量级时间复杂度的一种表示方法O(1)2.对数阶时间复杂度 O(logn)、O(n...
  • 算法效率

    2021-01-07 15:41:12
    算法效率(Efficientcy)的分析,指的是算法求解的一个问题所需要的时间和空间 时间资源和空间资源 如何衡量时间资源?建例一个客观的计算模型 计算模型(Turing 机、以及RAM(随机存储器))等 算法时间资源的估算 ...
  • 算法效率

    2020-12-29 09:53:36
    时间效率被称为时间复杂度,时间复杂度主要衡量一个算法的运行速度 空间效率 空间效率称为空间复杂度,空间复杂度主要衡量一个算法的额外空间 时间复杂度 计算机科学中,算法时间复杂度是一个函数,,它...
  • 时间复杂度是衡量算法执行效率种标准。但时间复杂度并不能跟性能划等号。在真实的软件开发中,即使在不降低时间复杂度的情况下,也可以通过一些优化手段,提升代码的执行效率。毕竟对于实际开发来说,即使是10%...
  • 算法时间复杂度的衡量

    千次阅读 2015-03-29 16:08:59
    算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。  随着计算机硬件和软件的提升,一个算法执行时间是算不太精确的。只能依据统计方法对算法进行估算。我们抛开硬件...
  • 时间复杂度是衡量算法执行效率种标准。但是,时间复杂度 != 性能。即便在不降低时间复杂度的情况下,也可以通过一些优化手段,提升代码的执行效率。即便是像10%、20%这样微小的性能提升,也是非常可观的。 算法...
  • 1.衡量一个算法好坏的标准在于其算法效率高,算法效率分为时间复杂度和空间复杂度,时间复杂度主要衡量一个算法的运行速度,空间复杂度主要衡量一个算法所需要的额外空间。一个算法好应该时间复杂度最低,空间复杂度...
  • 当代计算机的效率最常用 GFLOPS/W (每秒10亿次浮点运算每瓦)为单位衡量。 其中GFLOPS为性能单位,1GFLOPS 表示每秒可执行10亿次浮点运算,主流CPU、GPU(台式机)可达到几百上千GFLOPS的性能。 W是瓦,即...
  • 复杂度是衡量代码运行效率的重要的...假设一个任务,系统平均每秒新增10M数据,如果你的代码不能在1分钟内处理10M数据,系统就会发生时间爆炸和空间爆炸。因此需要尽可能地降低计算复杂度。 衡量复杂度的维度:时间...
  • 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储...
  •   算法效率分析的目的是,看算法是都可以执行,并在同一个问题存在多个算法的时候,可以从空间和时间性能上进行比较,以便从中挑选出较优的算法。   衡量算法效率的方法主要有两类:事后统计法和事前分析估算法...
  • 所以执行效率是很重要的一个考量标准. 接下来我们要讨论的:时间.空间复杂度分析就可以衡量执行效率,它是整个数据结构和算法学习的精髓. 二.为什么需要复杂度分析? 1. 测试结果非常依赖测试环境 不同硬件的测试...
  • 时间复杂度和空间复杂度是衡量算法的重要指标,对于排序算法特定算法,这篇文章整理了一些常见的基础性的指标,后续将以此为基础进行进一步的解释。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,667
精华内容 17,866
关键字:

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