精华内容
下载资源
问答
  • 算法效率评价

    千次阅读 2019-05-24 14:15:19
    1.算法效率评价标准 对于同样的编程问题,使用不同的算法最终的结果是一样的,但计算机计算过程是消耗的时间和空间却不一样,但是我们又不能去计算每个算法用的时间和空间,我们只能通过数学的方法来估算这个算法,...

    1.算法效率评价标准

    对于同样的编程问题,使用不同的算法最终的结果是一样的,但计算机计算过程是消耗的时间和空间却不一样,但是我们又不能去计算每个算法用的时间和空间,我们只能通过数学的方法来估算这个算法,这就是时间复杂度和空间复杂度产生的原由。
    时间复杂度和空间复杂度也是判断算法效率的重要指标;

    时间维度:是执行当前算法所消耗的时间,我们通常使用时间复杂度来描述.个人认为时间复杂度是[评估代码在cpu中的运行总行数]----T(n)=O(f(n))
    空间维度:是指执行当前需要占用多少=内存空间,我们通常用空间复杂度来描述.[评估代码在计算机内存中声明单元变量的总个数]-----S(n)=O(n)

    2.时间复杂度

    我们想要知道一个算法的「时间复杂度」,很多人首先想到的的方法就是把这个算法程序运行一遍,那么它所消耗的时间就自然而然知道了。
    这种方式可以吗?当然可以,不过它也有很多弊端。
    这种方式非常容易受运行环境的影响,在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。
    而且对测试时使用的数据规模也有很大关系。再者,并我们在写算法的时候,还没有办法完整的去运行呢。

    因此,另一种更为通用的方法就出来了:「 大O符号表示法 」,即 T(n) = O(f(n)) T(n) = O(f(n))
    其中f(n) 表示每行代码执行次数之和 而 O 表示正比例关系 这个公式的全称是:算法的渐进时间复杂度
    为什么可以这么去简化呢,因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。
    所以上面的例子中,如果n无限大的时候,T(n) = time(1+2n)中的常量1就没有意义了,倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。

    常见的时间复杂度量级有:
    常数阶O(1)
    对数阶O(logN)
    线性阶O(n)
    线性对数阶O(nlogN)
    平方阶O(n²)
    立方阶O(n³)
    K次方阶O(n^k)
    指数阶(2^n)

    3.空间复杂度

    既然时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。
    空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

    空间复杂度 O(1)

    {
    	int i = 1;
    	int j = 2;
    	++i;
    	j++;
    	int m = i + j;
    }
    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)
    

    空间复杂度 O(n)

    {
    	int[] m = new int[n]
    	for(i=1; i<=n; ++i)
    	{
    	   j = i;
    	   j++;
    	}
    }
    	这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,
    	这段代码的2-6行,虽然有循环,但没有再分配新的空间,
    	因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)
    
    展开全文
  • 数据结构算法和算法效率评价

    千次阅读 2017-11-24 14:25:20
    一、算法的基本概念 算法(Algorithm):是针对特定问题的问题求解步骤的一种描述。它是指令的有限序列;算法具有如下五个重要特征: 1.1、有穷性:有穷步骤,有穷计算时间; 1.2、确定性:每一条指令必须有确切的...

    一、算法的基本概念
    算法(Algorithm):是针对特定问题的问题求解步骤的一种描述。它是指令的有限序列;算法具有如下五个重要特征:
    1.1、有穷性:有穷步骤,有穷计算时间;
    1.2、确定性:每一条指令必须有确切的含义。换句话说就是:对于相同的输入必须得出相同的输出结果。
    1.3、可行性:算法是可行的,算法中描述的操作都是可以通过已经实现的基本运算执行有限次得到。
    1.4、输入
    1.5、输出

    一个好的算法有如下几个评价标准:
    1.正确性
    2.可读性
    3.健壮性
    4.效率与低存储量的要求

    二、算法效率的度量
    2.1时间复杂度:一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有的语句频度之和记作T(n),他是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级;算法中的基本运算(循环中的最深循坏内语句)的频度与T(n)同数量级。所以通常用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此时间的复杂度记作:
    T(n) = O(f(n))
    以上的O表示为T(n)的数量级。其严格的数学含义为:若T( n)和f(n)是定义在正整数集合上的两个函数。则存在正整数C和 n0,使得n>=n0,都满足0<=T(n)<=C*f( n)
    另外算法的时间复杂度不仅仅只是依赖以问题规模n,同时也取决于输入参数的性质(比如:数据的初始值);例如以下例子:
    在数组中A[0……N-1],查找最大值K

    i = 1;
    while(i>=0&&A[i] !=K)
        i--;
    return i;

    在此算法,时间复杂度不仅与最内层循环(i–)的赋值次数有关,还有A数组中的各元素值和目标最大值K有关:
    1.若A中没有与K相等的数,则算法中的(i–)的频度为f(n);
    2.若A的最后一个元素的值与K相等。则(i–)的频数为f(n) = 0;

    以下是常见的几个复杂度概念:
    最坏时间复杂度:在最坏情况下的时间复杂度;
    平均时间复杂度:所有可能输入实例在等概率出现的情况下,算法的期望运行时间。
    最好时间复杂度:在最好的情况下,算法的时间复杂度。
    一般情况下总是先考虑最坏时间复杂度,以保证算法的时间 复杂度不会超过这个最大值。

    时间复杂度的两个基本规则:
    1.加法法则:
    T(n)=T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)));

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

    3.常见的时间复杂度比较:
    O(1)< O(log2n)< O(n) < O(nlog(2n))< O(n^2)< O(n^3)< O(2^n)

    展开全文
  • 算法算法评价

    万次阅读 多人点赞 2019-07-05 20:42:11
    算法特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。具有以下性质: 1.有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内完成 2.确定性:算法中...

    一、算法的基本概念

     

    算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。具有以下性质:

    1.有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内完成

    2.确定性:算法中每条指令必须有确切的含义,不会产生二义性,对于相同的输入只能得出相同的输出。

    3.可行性:一个算法是可行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

    4.输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

    5.输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。

    我们的目标是设计出正确、可读、健壮、高效率、低存储量需求的算法!

     

    二、算法效率的度量:时间复杂度与空间复杂度

    1.时间复杂度

     

    (1)基本概念

           一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级,因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此,算法的时间复杂度记为

    T(n)=O(f(n))。

    式中,O的含义是T(n)的数量级,其严格的数学定义是:若T(n)和f(n)是定义在正整数集合上的两个函数,则存在正常数C和n0 ,使得当n≥n0 时,都满足0≤T(n)≤Cf(n)。

           算法的时间复杂度不仅依赖于问题的规模n,也取决于待输入数据的性质(如输入数据元素的初始状态)

           例如,在数组[0…n-1]中,查找给定值k的算法大致如下:

           (1)i=n-1;

           (2)while(i≥0&&(A[i]!=k)

           (3)i--;

           (4)return i;

    在上面的算法中语句(3)为基本运算,我们令t=i,则程序结束条件为t=n-1,也就是基本运算执行了n-1次,所以时间复杂度为O(n);

           当然,我们在上面也说过,时间复杂度也与输入元素取值有关,例如在上例中,若A中没有与k相同的元素,则(3)语句频度为f(n)=n;若A中最后一个元素为k,则语句(3)频度f(n)=0。

           据此,我们得到最坏时间复杂度,平均时间复杂度,最好时间复杂度。

     

    (2)最坏时间复杂度、平均时间复杂度、最好时间复杂度

    最坏时间复杂度:在最坏情况下,算法的时间复杂度。

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

    最好时间复杂度:在最好情况下,算法的时间复杂度

    一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。

     

    (3)计算规则

     

    a.加法规则

     

    b.乘法规则

     

    常用渐进时间复杂度为

     

    2.空间复杂度

           算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。渐进空间复杂度也常简称为空间复杂度,记为S(n)=O(g(n))

     

    展开全文
  • 算法效率的衡量

    千次阅读 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)
    顺序结构,时间复杂度按加法进行计算
    循环结构,时间复杂度按乘法进行计算
    分支结构,时间复杂度取最大值
    判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
    
    展开全文
  • 算法性能评价

    千次阅读 2019-09-23 08:05:25
    一种数据结构的优劣是由实现其各种运算的算法具体体现的,数据结构的分析实质上就是实现运算算法的分析,除了要验证算法是否正确解决该问题之外,还需要对算法效率作性能评价。在计算机程序设计中,算法分析是...
  • 算法评价

    千次阅读 2018-06-05 21:59:19
    算法评价法则1、正确性2、高效性3、空间性4、可读性算法效率通常,通过统计算法中基本操作重复执行的次数,就可近似的得到算法的执行效率,用O(n)表示,也称为时间复杂度...
  • 1.必须到机器上去计算,而且这个计算不只是一次,我们要用多组数据进行重复的运算,然后得到一个统计的结果,那么你要算上机器的时间。 2.肯定会有一些其他因素掩盖算法的本质。 2.事前分析估算法 通常比较算法...
  • 算法算法评价

    千次阅读 2018-04-16 22:02:52
     算法特定问题求解步骤的一种描述,它是指令的有限序列,其中  每一条指令表示一个或多个操作。此外,一个算法还具有下列5个重要的  特性。  (1)、有穷性  一个算法必须总是(任何合法的输入值)在执行...
  • 本节主要熟悉数据结构与算法中一般概念,然后熟悉算法效率分析的大O记法,知识结构如下图所示:什么是算法?1)算法的定义算法(Algorithm),指的是特定问题求解步骤的一种描述。 在数学上,它是运算步骤的有限序
  • 算法效率衡量标准(时间复杂度)

    千次阅读 2019-08-14 11:20:27
    如果对于解决一个问题有2种算法算法1的执行时间小于算法2,这并不能代表算法1优于算法2。假设执行算法1的计算机性能和环境都低于执行算法2的计算机的性能和环境,那么算法1可能执行的时间会更长。所以可以看出仅仅...
  • 一些用于理解的概念: 内排序和外排序 在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序; 在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的...1. 性能评价标准
  • 衡量查找算法效率的主要标准是( )。 正确答案: C 你的答案: C (正确) 元素个数 所需的存储量 均匀查找长度 算法难易程度 添加笔记 求解答(2) 收藏 纠错
  • 本课主题: 算法效率的度量和存储空间需求教学目的: 掌握算法的渐近时间复杂度和空间复杂度的意义与作用教学重点: 渐近时间复杂度的意义与作用及计算方法教学难点: 渐近时间复杂度的意义授课内容:一、算法效率的...
  • 算法效率衡量

    千次阅读 2018-01-21 14:30:32
    对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以得出结论:实现算法程序的
  • 推荐算法常用评价指标

    千次阅读 2020-04-24 09:09:55
    因此,单纯靠准确率来评价一个算法模型是远远不够科学全面的。 指标计算tips: 1.计算auc的时候就必须用概率,不能用标签的。auc是计算输出分数的排序能力,会穷举所有可能的阈值。 2.auc的直观解释是任取一个正样本...
  • 数据结构基本概念 基本概念和术语 数据:数据是信息的载体,信息是数据的内涵 数据元素:数据的基本单位,一个数据... 算法效率 时间复杂度T(n) 空间复杂度S(n) 算法原地工作是指算法所需的辅助空间为常量,即S(n)=O(1)
  • data的各个feature进行预处理 1. feature的选择:用相关性、基尼系数、...4. 可以数据进行降维处理,映射到低维度空间进行展示,观察数据形状,帮助选择聚类算法 降维的一些选择: 线性方法,PCA 非线性特征十分
  • 常用进程调度算法的分析与评价

    千次阅读 2010-12-10 15:42:00
    本文详细地讨论了四种常用进程调度算法的基本思想,并进行了分析和评价。 关键词  进程调度算法,分析,评价1 引言 进程调度是系统内部的低级调度,进程调度的策略通常有先来先服务算法、时间片轮转算法、...
  • 图像增强算法效果评价指标及实现

    万次阅读 2017-10-29 08:59:17
    对于一种图像处理方法,怎么样来判断该算法效果的好坏呢?除了人眼本身的观察,还可以用某种指标来量化评判,本文将总结一下图像质量评判的方法及实现。 图像质量评价分类(IQA:image quality assessment): ...
  • 数据结构算法评价四个标准

    万次阅读 热门讨论 2015-08-30 23:52:35
     输入非法数据,算法也能适当地做出反应后进行处理,不会产生预料不到的运行结果。 数据的形式多种多样,算   法可能面临着接受各种各样的数据,当算法接收到不适合算法处理的数据,算法本身该如何处理呢? ...
  • 销售数据是随着时间变化的序列,通过未来的销售进行预测,方便人员、物料等各种资源投入的把控,控制好库存,减少浪费,也可以制定未来的营运策略,提高管理效率。 这里使用ARMA(AutoRegressive Moving ...
  • 算法评价: 时间效率: 一个算法中语句重复执行的次数叫做语句频度 算法中基本操作重复执行的次数依据算法中最大语句频度来计算,她是问题规模n的某个函数f(n),算法的时间量度记作T(n) = O(f(n)).成为时间复
  • 如何评价一个算法的好坏

    千次阅读 2019-04-27 21:38:39
    这个算法还需要足够健壮,即当输入的数据非法或不合理时,也能适当的做出正确的反应或进行相应的处理 最后它还必须拥有高效率和低存储量要求。 也就是所谓的时间复杂度和空间复杂度 1.时间复杂度 定义:在计算机科学...
  • 1.面向用户(User-oriented)的准则和评价 (1)周转时间(Turnaround Time)短 它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始, 到作业完成为止的这段时间间隔。 周转时间 Ti = ...
  • 时间复杂度-算法评价的标准

    千次阅读 2018-09-21 13:45:00
    前言:算法,一直是每个程序员的心病,确是程序的核心,很多人觉得算法很难,没错,但是世界上真的有很难的事情吗?如果不去尝试,只去抱怨,不去尝试,我觉得可能一辈子也就只能当一名普通的程序员了。有一句老话说...
  • 遗传算法的解读

    千次阅读 2011-01-26 13:47:00
    复杂的问题,海量的数据,或者求解时间上的限制,常常会使人们不得不选择一种智能算法去求解近似最优解,像模拟退火、神经网络、蚁群算法、遗传算法等。简单的了解了下这几种常见的求近似最优解的智能算法后,我...
  • 排序算法  排序是将一组无序的记录序列调整为有序的记录序列的操作,可以方便查找...一般进行的是内部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。基于不同的扩大有序序列的方法,内部排序大致可以
  • 算法分析指的是:对算法在运行时间和存储空间这两种资源的利用效率进行研究。 即时间效率和空间效率。   时间效率算法运行有多快; 空间效率算法运行时需要多少额外的存储空间。 (时间效率也叫时间复杂度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,821
精华内容 20,328
关键字:

对算法效率进行评价