<span role="heading" aria-level="2">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(n²)。

<!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>