最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 【得物技术】算法入门一:算法的好坏?复杂度告诉你

    正文概述 掘金(得物技术)   2021-04-10   76

    什么是算法

    百度百科对算法的定义是 “解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。”

    简单的来讲,算法就是解决一个问题所用的方法。比如对于数组排序问题,有多种排序方法可以达到使元素有序排列的目的,每一种正确的排序方法都能称之为一个算法。

    如何衡量算法的好坏

    一个问题既然可以通过多种算法来解决,那么如何衡量哪个算法更好呢?

    显然一个算法执行时间越短,占用的内存空间越小,那么它就是更好的算法。

    通常有两种方法来比较:事前分析和事后统计。事后统计就是指先编写好算法,并运行监控其指标,该方法的问题在于受运行环境、电脑硬件干扰,会掩盖算法本身的优劣。因此科学的方法是通过数学分析的方法来评估算法的好坏。

    前面说到算法执行时间越短,占用内存空间越小,算法越好。对应的,我们常常用时间复杂度来代表算法执行时间,空间复杂度代表算法占用的内存空间。

    时间复杂度

    一般来讲,一个算法花费的时间与其中执行的语句的次数成正比,一个算法中的语句执行次数称为时间频度,用 T(n) 来表示。

    比如有 func 函数如下:

    function func(n) {
        for(let i = 0; i < n; i ++) {       // 执行n+1次
            console.log('Hello World!')     // 执行n次
        }
        return                              // 执行1次
    }
    

    对于 func 来讲,该算法运行时,共执行了 2n+2 次运算,那么该算法的时间频度 T(n) = 2n + 2, n 为算法输入的大小,即输入的数据规模,当 n 不断变化时,T(n) 也会随之变化。

    假设有某个辅助函数 f(n), 当 n 趋于无穷大时,总有 T(n) <= C * f(n) (C 为常数) 成立,即 T(n) 的上界是 C * f(n),记作 T(n) = O(f(n)) ,称 O(f(n)) 为算法的渐进时间复杂度,O 表示正比例关系,f(n) 表示代码执行次数之和, 这种表示方法叫做 「 大O符号表示法 」。

    所以对于函数 func 来讲,有 T(n) = O(2n+2),可以简化为 T(n) = O(n)。为什么可以简化呢,是因为大O表示法只是用来代表执行时间的增长变化趋势,当 n 无穷大时,2n+2 中的常量就没有意义了,同时因为符号O中隐藏着常数C,所以 n 的系数2可以省略到C中。f(n) 中 n 一般不加系数。同理,我们可以得到 O(2n²+n+1) = O(2n²) = O(n²)。如果把 T(n) 表示成一棵树,O(f(n)) 表示的就是树干,其他的细枝末节对于复杂度的影响远小于树干。

    一般来讲,衡量一个算法的复杂度,我们往往只需要判断循环结构里基本操作发生了多少次,就能代表该算法的时间复杂度。

    常见的时间复杂度

    • 常数阶 O(1)

    加减乘除(eg. i++, i--)、数组寻址(eg. array[10])、赋值操作(eg. a=1)等都属于常数级的复杂度,简言之如果没有循环等复杂结构,不随输入数量级 n 变化的操作,该代码的时间复杂度都属于常数级复杂度,不管这种代码有多少行。

    • 对数阶 O(logn)
    function func(n) {
        let i = 0;
        while(i < n) {
            i *= 2;
        }
    }
    

    对如上 func 函数来讲,在 while 循环中,假设当循环到第 m 次时, 有 i = n ,即 2 的 m 次方等于 n,可知 m = logn (往往将以2为底省略),即 while 循环内的操作运行了 logn 次,该算法的时间复杂度即为logn 。

    • 线性阶 O(n)
    function func(n) {
        sum = 0;
        for(let i = 0; i < n; i++) {
            sum += i;
        }
        return sum; 
    }
    

    如上 func 函数,for 循环中的原子操纵执行了 n 次,该算法的时间复杂度即为 O(n)。

    • 线性对数阶 O(nlogn)
    function func(n) {
        for(let m = 1; m < n; m++)
        {
            let i = 1;
            while(i < n)
            {
                i = i * 2;
            }
        }
    }
    

    如上函数,有双层循环结构,显然根据之前的时间复杂度可以推断出来该算法的时间复杂度为 O(nlogn) ,当然上面的函数是为了凑这个复杂度而凑的,并没有实际的意义。

    • 平方阶 O(n²)
    function func(n) {
        let sum = 0;
        for(let i = 0; i < n; i ++) {
            for(let j = 0; j < n; j ++) {
                sum += i * j;
            }
        }
        return sun;
    }
    

    如上函数,有双层循环结构,第5行代码,共循环运行了 n² 次,所以该算法的时间复杂度为 O(n²)。

    • 立方阶 O(n³),K次方阶O(n^k)

    和平方阶同理,有多层循环结构,该循环结构中的原子操作循环的次数。 常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n²)<Ο(n³)<…<Ο(2^n)<Ο(n!)。

    空间复杂度

    空间复杂度是对一个算法在运行过程中辅助变量临时占用存储空间大小的一个量度。空间复杂度和时间复杂度同理,也采用大O表示法,比较常用的有:O(1)、O(n)。

    • O(1)

    算法执行时所需要的临时空间不随着数据规模 n 的大小变化,则算法的空间复杂度为 O(1),比如对于数组求和,其中 sum 和 i 都是临时变量,所需要的空间不随array长度的大小而变化,所以该函数的空间复杂度为 O(1)。

    function func(array) {
        let sum = 0;
        for(let i = 0; i < array.length; i++) {
            sum += array[i];
        }
        return sum;
    }
    
    • O(n)
    function func(array) {
        let new_array = [...array];
        return new_array;
    }
    

    如上函数是复制了输入 array 数组,返回复制的数组,在函数中,创建了 array.length 长度的新数组 new_array,该算法的空间复杂度和原数组 array 的长度成正比,故该算法的时间复杂度为 O(n),n 代表数组 array 的长度。

    至此我们已经了解了常见的时间复杂度和空间复杂度,时间复杂度的分析需要根据具体的算法来分析,有了这个基础,我们就能针对实际的算法进行分析啦!

    参考

    www.zhihu.com/question/21…

    zhuanlan.zhihu.com/p/50479555

    www.jianshu.com/p/f4cca5ce0…

    blog.csdn.net/zolalad/art…

    文|hustlmn

    关注得物技术,携手走向技术的云端


    起源地 » 【得物技术】算法入门一:算法的好坏?复杂度告诉你

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元