• 炮制数万斤毒豆芽 广州三个黑作坊被警方捣毁 2019-08-02
  • 2018年5月后期资助项目结项名单 2019-08-01
  • 女性之声——全国妇联 2019-07-31
  • 你才是“蠢货”!土地是自然存在的地球的一部分,并不是人类劳动成果,哪来价值?土地不是劳动成果,没有价值,正如空气和阳光不是劳动成果,没有价值一样。懂吗... 2019-07-31
  • 学习贯彻落实习近平总书记重要讲话精神·奥一网(oeeee.com) 2019-07-23
  • 新生儿6种异常不用慌 2019-07-15
  • 海尔发行境外上市外资股获批 2019-07-15
  • 朝鲜将变得很富有?外媒驱动引擎是中国而非美国 2019-07-12
  • 【加拿大房产网加拿大新房加拿大房产信息网】 2019-06-22
  • 中美研究人员发现新型狗流感病毒 2019-05-29
  • 豫园商城升级改造:这些楼顶可见最好的风景--旅游频道 2019-05-14
  • 头条 —频道 春城壹网 七彩云南 一网天下 2019-05-14
  • 人为某种意识而奋斗是幸福的,获得成绩或成就更幸福。 2019-05-10
  • 【专题】省违反中央八项规定精神和“四风”问题线索举报平台 2019-05-09
  • 确定这是热身赛?吴前拼到大腿抽筋 拆绷带继续干 2019-05-09
  • js算法初窥07(算法复杂度)

      算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空间复杂度则是指算法中用来存储的数据结构所占用的空间。往往一个时间复杂度比较低的算法拥有着较高的空间复杂度,两者是互相影响的,我们前面讲解数据结构中的一些例子和代码也足以说明这一点。本文会简单介绍一下用于描述算法的性能和复杂程度的大O表示法。

      我们先来看一段简单的代码,来帮助我们理解什么是大O表示法:

    function increment(num) {
        return ++num;
    }
    
    console.log(increment(1));

      上面的代码声明了一个函数,然后调用它。这样的代码无论我们传入的参数是什么,它都会返回自增后的结果。也就是说该函数的执行时间跟我们传入的参数没有任何关系,执行的时间都是X。因此,我们称该函数的复杂度是O(1),常数的。

      我们再来看看前面讲过的顺序搜索算法,我们直接把代码拿过来用就好了。

    //顺序搜索
    function sequentialSearch(array,item) {
        for(var i = 0; i < array.length; i++) {
            if(item === array[i]) {
                return i;
            };
        };
        return -1;
    };

      现在我们假设要搜索的数组是[1,2,3...9,10],然后我们搜索1这个元素,那么在第一次判断时就能找到想要搜索的元素。那么我们这里先假设每执行一次循环的开销是1。那么我们还想搜索11,数组中没有这个元素,sequentialSearch 就会执行十次遍历整个数组,发现没有后返回-1。那么在最坏的情况下,数组的长度大小决定了算法的搜索时间。这样的函数的时间复杂度就是O(n),线性的,这里的n就是数组的长度。

      那么,我们来稍微修改一下sequentialSearch让它可以计算开销:

    //顺序搜索
    function sequentialSearch(array,item) {
        var cost = 0;
        for(var i = 0; i < array.length; i++) {
            cost++;
            if(item === array[i]) {
                return i;
            };
        };
        console.log(array.length,cost);
        return -1;
    };
    
    sequentialSearch([1,2,3,4,5,6,7,8,9,10],11);

      很简单,就是加上了一个cost变量来计数。那么我们下面再来看看冒泡排序的时间复杂度是怎样的,这里我们不再浪费篇幅,直接在代码中加入计数器:

    function swap(array,index1,index2) {
        var aux = array[index1];
        array[index1] = array[index2];
        array[index2] = aux;
    }
    
    function bubbleSort(array) {
        var length = array.length;
        var cost = 0;
        for (var i = 0; i < length; i++) {
            cost++;
            for (var j = 0; j < length - 1; j++) {
                cost++;
                if(array[j] > array[j + 1]) {
                    swap(array,j,j+1);
                }
            }
        }
    
        console.log(length,cost);
    }
    
    bubbleSort([2,3,4,1,8,7,9,10]);

      代码本身没什么好说的,我们发现,如果数组的长度是8,那么我们排序所消耗的时间就是64,如果长度是10,消耗的时间就是100?;痪浠八?,冒泡排序的时间复杂度就是数组长度的平方,也就是O(n2)。

    <!DOCTYPE html>
    <html>
    <head lang="en">
        <meta charset="UTF-8">
        <style>
            body { background-color: #DDDDDD; font: 30px sans-serif; }
        </style>
        <script type="text/javascript" src="https://www.google.com/jsapi"></script>
        <script type="text/javascript">
            google.load('visualization', '1.0', {'packages':['corechart']});
    google.setOnLoadCallback(drawChart);
    
    function drawChart() {
    
        var data = new google.visualization.DataTable();
        data.addColumn('string', 'n');
        data.addColumn('number', 'O(1)');
        data.addColumn('number', 'O(log n)');
        data.addColumn('number', 'O(n)');
        data.addColumn('number', 'O(n log n)');
        data.addColumn('number', 'O(n^2)');
        data.addColumn('number', 'O(2^n)');
    
        for (var i = 0; i <= 30; i++) {
            data.addRow([i+'', 1, Math.log(i), i, Math.log(i)*i, Math.pow(i,2), Math.pow(2,i)]);
        }
    
        var options = {'title':'Big O Notation Complexity Chart',
            'width':700,
            'height':600,
            'backgroundColor':{stroke:'#CCC',strokeWidth:1},
            'curveType':'function',
            'hAxis':{
                title:'Elements (n)',
                showTextEvery:5
            },
            'vAxis':{
                title:'Operations',
                viewWindowMode:'explicit',
                viewWindow:{min:0,max:450}
            }
        };
    
        var chart = new google.visualization.LineChart(document.getElementById('chart_div'));
        chart.draw(data, options);
    }
        </script>
    </head>
    <body>
    <div id='chart_div'></div>
    </body>
    </html>

      上面的代码是用js画的一幅图,其中有一些常用的大O表示法所对应的时间复杂度,大家可以把代码COPY到本地自行去看一下,这样会才会对大O表示法有更好的理解,为了偷点懒,也为了大家可以确实的自己去看一下图标。我这里不会把图给大家贴上的。

      下面给大家贴上几张图,来看看我们之前学习的一些数据结构和算法的时间复杂度是怎样的。

    1、常用数据结构的时间复杂度

    2、图的时间复杂度

    表格中的V代表顶点,E代表边。

    3、排序算法

    4、搜索算法的时间复杂度

      终于,我们了解了几乎我们前面学过的所有的数据结构和算法的时间复杂度,这样我们在选择算法的时候可以更确切地评估它的效率。

      那么,我们本系列的文章也将告一段落。后面准备深入的学习一下CSS??赡芑岚哑渲幸恍┍冉嫌幸馑嫉牡胤教隼从氪蠹曳窒?。

     

      最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

      最后,感谢大家的阅读。如果您觉得或许还有那么点用处,可以把我的主页加入你的收藏夹中以便需要的时候可以快速的找到。

    posted @ 2018-05-30 16:13 Zaking 阅读(...) 评论(...) 编辑 收藏
  • 炮制数万斤毒豆芽 广州三个黑作坊被警方捣毁 2019-08-02
  • 2018年5月后期资助项目结项名单 2019-08-01
  • 女性之声——全国妇联 2019-07-31
  • 你才是“蠢货”!土地是自然存在的地球的一部分,并不是人类劳动成果,哪来价值?土地不是劳动成果,没有价值,正如空气和阳光不是劳动成果,没有价值一样。懂吗... 2019-07-31
  • 学习贯彻落实习近平总书记重要讲话精神·奥一网(oeeee.com) 2019-07-23
  • 新生儿6种异常不用慌 2019-07-15
  • 海尔发行境外上市外资股获批 2019-07-15
  • 朝鲜将变得很富有?外媒驱动引擎是中国而非美国 2019-07-12
  • 【加拿大房产网加拿大新房加拿大房产信息网】 2019-06-22
  • 中美研究人员发现新型狗流感病毒 2019-05-29
  • 豫园商城升级改造:这些楼顶可见最好的风景--旅游频道 2019-05-14
  • 头条 —频道 春城壹网 七彩云南 一网天下 2019-05-14
  • 人为某种意识而奋斗是幸福的,获得成绩或成就更幸福。 2019-05-10
  • 【专题】省违反中央八项规定精神和“四风”问题线索举报平台 2019-05-09
  • 确定这是热身赛?吴前拼到大腿抽筋 拆绷带继续干 2019-05-09
  • 888现金棋牌游戏 江苏新11选5开奖直播 极速快三软件下载 就爱棋牌游戏 sg飞艇是哪里开的 天津时时群 山东体彩手机在线 七星彩局王图纸长条 四川时时规则 华东6十1开奖号码 赛车赛事观看软件 大上海时时平台 安徽时时一天几期 云南时时彩开奖结果今天 gpk电子平台 vr3分彩走势