• 豫园商城升级改造:这些楼顶可见最好的风景--旅游频道 2019-05-14
  • 头条 —频道 春城壹网 七彩云南 一网天下 2019-05-14
  • 人为某种意识而奋斗是幸福的,获得成绩或成就更幸福。 2019-05-10
  • 【专题】省违反中央八项规定精神和“四风”问题线索举报平台 2019-05-09
  • 确定这是热身赛?吴前拼到大腿抽筋 拆绷带继续干 2019-05-09
  • 应对排放新规 大众德国工厂计划短暂停产 2019-04-26
  • 一师一团土地确权登记颁证工作全面展开 2019-04-26
  • 一语惊坛(5月31日):“我们不一样”,中国向世界许下一个承诺。 2019-04-22
  • 俄罗斯世界杯F组:球迷风采 2019-04-10
  • 5月份国民经济数据发布:中国经济持续稳中向好 2019-04-10
  • 贵州宣讲十九大:干部争当宣讲员 群众心窝暖洋洋 2019-03-25
  • 别空谈,说说看,这个“简单的逻辑关系”是什么关系? 2019-03-25
  • 快过闪电,MIUI 10与MIUI 9速度对比 2019-03-21
  • 泽州去年“免费教育”资金达5211万元 2019-03-19
  • 看你这么可怜,再提示你一下:你重孙算1,父母为2,父母的父母为4,父母的父母的父母为8…… 2019-03-19
  • js算法初窥07(算法复杂度)

    快乐彩开奖号码 www.752o.com   算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空间复杂度则是指算法中用来存储的数据结构所占用的空间。往往一个时间复杂度比较低的算法拥有着较高的空间复杂度,两者是互相影响的,我们前面讲解数据结构中的一些例子和代码也足以说明这一点。本文会简单介绍一下用于描述算法的性能和复杂程度的大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-05-14
  • 头条 —频道 春城壹网 七彩云南 一网天下 2019-05-14
  • 人为某种意识而奋斗是幸福的,获得成绩或成就更幸福。 2019-05-10
  • 【专题】省违反中央八项规定精神和“四风”问题线索举报平台 2019-05-09
  • 确定这是热身赛?吴前拼到大腿抽筋 拆绷带继续干 2019-05-09
  • 应对排放新规 大众德国工厂计划短暂停产 2019-04-26
  • 一师一团土地确权登记颁证工作全面展开 2019-04-26
  • 一语惊坛(5月31日):“我们不一样”,中国向世界许下一个承诺。 2019-04-22
  • 俄罗斯世界杯F组:球迷风采 2019-04-10
  • 5月份国民经济数据发布:中国经济持续稳中向好 2019-04-10
  • 贵州宣讲十九大:干部争当宣讲员 群众心窝暖洋洋 2019-03-25
  • 别空谈,说说看,这个“简单的逻辑关系”是什么关系? 2019-03-25
  • 快过闪电,MIUI 10与MIUI 9速度对比 2019-03-21
  • 泽州去年“免费教育”资金达5211万元 2019-03-19
  • 看你这么可怜,再提示你一下:你重孙算1,父母为2,父母的父母为4,父母的父母的父母为8…… 2019-03-19
  • 北京赛车pk10超级技巧 北京五分彩怎么玩 重庆幸运农场预测软件手机版下载 大乐透机选新浪爱彩 排列三跨度走势图表带坐标连线图 pc蛋蛋幸运28怎么挂机 35选7广东走势图 七星彩查询 北京赛车是正规彩票吗 体彩排列3出号走势图 体彩超级大乐透走势图 湖南幸运赛车破解版 3d开奖结果走势图 七星彩玩法 捕鱼达人无限金币版 360德州扑克