美文网首页
2.算法简介

2.算法简介

作者: 穹生变 | 来源:发表于2021-02-27 14:48 被阅读0次

      算法:根据一定的条件,对一些数据进行计算,并得到需要的结果。


      同一个问题可以有多种算法来解决,我们在设计算法是需要追求两个目标:1.花最少的时间。2.占用最少的内存空间。


      在算法设计中我们需要进行算法分析,也就是时间耗费的分析和空间耗费的分析。时间耗费分析称为时间复杂度分析。空间耗费分析称为空间复杂度分析。


      有两种时间复杂度分析的方法:事后分析法和事前分析法。
    事后分析法即在程序开始和结束分别取时间,然后查看算法运行时长。这种方法影响因素不确定性多,有缺陷。
    事前分析法是根据统计法对算法进行估算。


    程序在计算机中运行的时间消耗和一下几方面有关系:
    1.算法采用的策略和方案。
    2.编译产生的代码质量。
    3.问题的输入规模。
    4.机器执行指令的速度。
    其中只有1和3是我们设计算法时需要考虑的因素。


    我们在比较算法随输入规模增长的增量时,可得出以下规则:
    1.算法函数中常熟可以忽略。
    2.算法函数中最高次幂的常数因子可以忽略。
    3.算法函数中最高次幂越小,算法越高效。


    在进行算法分析时我们应该明确,执行次数越多,那么程序耗时越长。
    次数《==》耗时
    算法时间复杂度就是算法的时间度量我们使用大O记法。即T(n)=O(f(n));
    在算法的大O阶的分析过程中我们有一下规则:
    1.用常数1取代运行时间中所有加法常数。
    2.在修改后的运行次数中只保留高阶项。
    3.如果最高阶项存在且常数因子不为1,则去掉与这个阶项相乘的常数因子。
    例如:算法1,3次-->O(1)。算法2,n+3次-->O(n)。算法3,n^2+3-->O(n^2)


    常见的大O阶:
    1.线型阶:随着输入的增长执行次数呈线型增长。如单层循环。
    2.平方阶:抛物线。双层循环。
    3.立方阶:抛物线。三层循环。
    4.对数阶:抛物线。
    5.常数阶:不涉及循环操作,基本都是他。
    他们的时间复杂度顺序:O(1)<O(logn)<O(n)<O(n^2)<O(n^3)。一般如果我们分析复杂度为平方及以上的,我们都认为算法是不可取的,需要进行优化。


    java中各种数据对于空间的占用情况:
    1.基本数据类型内存占用

    image.png
    2.计算机访问内存的方式都是一次读取一个字节。
    3.一个引用即一个变量占用8个字节。
    4.创建一个对象,除去对象中储存数据占用的内存,对象本身也需要16个字节来存储头信息。
    5.一般内存的使用如果不够8个字节,都会补充为8字节。
    6.Java中数组被限定为对象,他们需要16个字节存头信息,4个字节存长度,以及4个填充字节。除了数组中存储的数据需要的内存,需要占用24个字节。

    空间复杂度分析就是算法占用内存大小的分析。开发中如果不是嵌入式开发,一般不需要做算法空间复杂度的分析。

    相关文章

      网友评论

          本文标题:2.算法简介

          本文链接:https://www.haomeiwen.com/subject/chcifltx.html