美文网首页
大O表示法

大O表示法

作者: 姚冰coding | 来源:发表于2017-03-31 19:22 被阅读0次

    讨论算法必提到O(),不太懂,尝试理解一下。

    大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)。但对于小数据量,插入排序实际上更快一些,特别是那些已经有一部分数据是排序好的数组。

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

    参考资料:

    相关文章

      网友评论

          本文标题:大O表示法

          本文链接:https://www.haomeiwen.com/subject/hnwvottx.html