第十一章 算法复杂度

11.1 大O表示法?

????????它用于描述算法的性能和复杂程度。分析算法时，时常遇到以下几类函数：

11.1.1 理解大O表示法

????????如何衡量算法的效率？通常是用资源，例如CPU（时间）占用、内存占用、硬盘占用和网络
占用。当讨论大O表示法时，一般考虑的是CPU（时间）占用。
????????让我们试着用一些例子来理解大O表示法的规则。

1. O(1)

function increment(num){
    return ++num
}

????????假设运行increment(1)函数，执行时间等于X。如果再用不同的参数（例如2）运行一次
increment函数，执行时间依然是X。和参数无关，increment函数的性能都一样。因此，我们
说上述函数的复杂度是O(1)（常数）

2. O(n)

function sequentialSearch(array,item){
    console.log(item)
    var cost = 0
    for(var i =0;i<array.length;i++){    //{1}
        cost++
        if(item === array[i]){
           console.log('cost for sequentialSearch with input size ' +array.length+ ' is '+cost)
           return i
        }
    }
    console.log('cost for sequentialSearch with input size ' +array.length+ ' is '+cost)
    return -1
}

????????如果将含10个元素的数组（[1, ..., 10]）传递给该函数，假如搜索1这个元素，那么，第一次判断时就能找到想要搜索的元素。在这里我们假设每执行一次行{1} ，开销是 1。
????????现在，假如要搜索元素11。行{1}会执行10次（遍历数组中所有的值，并且找不到要搜索的
元素，因而结果返回 -1）。如果行{1}的开销是1，那么它执行10次的开销就是10，10倍于第一种
假设。
????????现在，假如该数组有1000个元素（[1, ..., 1000]）。搜索1001的结果是行{1}执行了1000
次（然后返回-1）。
????????注意，sequentialSearch函数执行的总开销取决于数组元素的个数（数组大小），而且也
和搜索的值有关。如果是查找数组中存在的值，行{1}会执行几次呢？如果查找的是数组中不存
在的值，那么行{1}就会执行和数组大小一样多次，这就是通常所说的最坏情况。
????????最坏情况下，如果数组大小是10，开销就是10；如果数组大小是1000，开销就是1000。可以
得出sequentialSearch函数的时间复杂度是O(n)，n是（输入）数组的大小。

3. O(n2)
用冒泡排序做O(n2)的例子：

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++){ //{1}
        cost++;
        for (var j=0; j<length-1; j++ ){ //{2}
            cost++;
            if (array[j] > array[j+1]){
                swap(array, j, j+1);
            }
        }
    }
    console.log('cost for bubbleSort with input size ' + length + ' is ' + cost);
}

????????如果用大小为5的数组执行bubbleSort，开销是 5的二次方。如果用大小为10的数组执行
bubbleSort，开销就是 10的二次方。数组大小为n，开销就是n的二次方。

11.1.2 时间复杂度比较

1. 数据结构

2. 图

3. 排序算法

4. 搜索算法