大O表示法

描述算法的性能和复杂度。常用O表示。一般考虑为cpu时间占用。

WX20170331-145138.png

1.O(1)

算法执行时间和参数无关，函数性能一样，时间复杂度称为O(1)。
例：

function increaseNum(num){
    return ++num
}

假如执行时间为x，不管传入任何值，执行时间都是x。

2.O(n)

O(n),算法的执行时间呈线性关系。如果你有 100 个元素，这种算法就要做 100 次工作。数据量翻倍那么运行时间也翻倍。例子：线性查找。

function search(array, item) {
    var cost = 0;
    for (var i = 0; i < array.length; i++) {
        cost++;
        if (item === array[i]) {
            return i;
        }
    }

}

时间花费cost和输入的array有关，呈线性关系。寻找item要把array遍历一次。

3.O(n^2)

O(n^2 ), 有点慢。如果你有 100 个元素，这种算法需要做 100^2 = 10000 次工作。数据量 x 2 会导致运行时间 x 4 (因为 2 的 2 次方等于 4)。例子：循环套循环的算法，比如插入排序。

//数组的交换，所以要引入index1，index2.数组内部元素的交换
function swap(array, index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}
//冒泡排序O(n^2)
function bubbleSort(array) {
    var length = array.length;
    for (var i = 0; i < length; i++) {
        for (var j = 0; j < length - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
    return array;
}

大部分情况下你用直觉就可以知道一个算法的大 O 表示法。比如说，如果你的代码用一个循环遍历你输入的每个元素，那么这个算法就是 O(n)。如果是循环套循环，那就是 O(n^2)。如果 3 个循环套在一起就是 O(n^3)，以此类推。

注意，大 O 表示法只是一种估算，当数据量大的时候才有用。举个例子，[插入排序](Insertion Sort/)的最糟情况运行时间是 O(n^2)。理论上来说它的运行时间比[归并排序](Merge Sort/)要慢一些。归并排序是 O(n log n)。但对于小数据量，插入排序实际上更快一些，特别是那些已经有一部分数据是排序好的数组。

如果你看完没懂，也不要太纠结了。这种东西仅仅在比较两种算法哪种更好的时候才有点用。但归根结底，你还是要实际测试之后才能得出结论。而且如果数据量相对较小，哪怕算法比较慢，在实际使用也不会造成太大的问题。

参考资料：