时间复杂度解析

算法的复杂度算是我们入门算法的第一课了，之前了解的有限，现在综合整理一下相关的概念：

算法复杂度分为时间复杂度和空间复杂度。

其作用：
时间复杂度是指执行算法所需要的计算工作量；
而空间复杂度是指执行这个算法所需要的内存空间。

本篇只来分析一下时间复杂度，当程序要处理的数据增长时，基本操作要重复执行的次数必定也会增长，那么这个执行次数在以什么样的数量级增长，对性能的影响有多少呢？

我们约定使用大O表示法表示一下常见的时间复杂度量级，表示代码执行时间随数据规模增长的变化趋势，也称为渐进时间复杂度。常见的量级如下：

常数阶 O(1)

线性阶 O(n)

对数阶 O(logn)

线性对数阶 O(nlogn)

平方阶 O(n^2)
复制代码

1、 O(1)

常数阶，这种复杂度无论数据规模n如何增长，计算时间是不变的。

const add = n => n++
复制代码

2、 O(n)

线性复杂度，随着数据规模n的增长，计算时间也会随着n线性增长。比较典型的例子就是线性查找。

const linearSearch = (arr, target) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i
        }
    }
    return false
}
复制代码

3、O(logn)

对数复杂度，随着问题规模n的增长，计算时间也会随着n对数级增长。典型的例子就是二分查找法。

O(logn) 时间复杂度的算法随着数据规模的增⼤，它的优势就越明显。

function binarySearch(arr, target){
    let max = arr.length - 1
    let min = 0
    while(min <= max){
        let mid = Math.floor((max + min)/2)
        if(target < arr[mid]){
            max = mid -1
        }else if(target > arr[mid]){
            min = mid + 1
        }else{
            return mid
        }
    }
    return -1
}
复制代码

4、O(nlogn)

线性对数复杂度，随着数据规模n的增长，计算时间也会随着n呈线性对数级增长。典型的代表就是归并排序。

const mergeSort = array => {
    const len = array.length
    if(len < 2){
        return len
    }
    const mid = Math.floor(len/2)
    const first = array.slice(0,mid)
    const last = array.slice(mid)
    
    return merge(mergeSort(fist),mergeSort(last))
    
    function merge(left,right){
        var result = [];
        while(left.length && right.length){
            if(left[0] <= right[0]){
                result.push(left.shift())
            }else{
                result.push(right.shift())
            }
        }
        
        while(left.length){
            result.push(left.shift());
        }
        
        while(right.length){
            result.push(right.shift());
        }
        return result;
    }
}
复制代码

5、O(n^2)

平方级复杂度,典型情况是当存在双重循环的时候，也就是把O(n)的代码再嵌套一遍，他的时间复杂度就是O(n^2),比如冒泡排序算法。

// 比较两个相邻的元素。如果第一个比第二个大，就交换他们两个，最后一个元素是最大值
function bubleSort(arr){
    var temp;
    for(var i=0;i<arr.length;i++){
        for(var j=0;j<arr.length-i-1;j++){
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    };
    return arr;
}
复制代码