js算法初窥07(算法复杂度)

  1. 云栖社区>
  2. 博客>
  3. 正文

js算法初窥07(算法复杂度)

zaking 2018-05-30 16:13:00 浏览648
展开阅读全文

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

 

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

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

一只想要飞得更高的小菜鸟

网友评论

登录后评论
0/500
评论
zaking
+ 关注