算法学习

# 时间复杂度和空间复杂度

评价算法的两个重要依据——时间复杂度和空间复杂度。

# 时间复杂度

对代码执行次数的量度

# 空间复杂度

在运行过程中临时占用存储空间大小的量度

# 时间复杂度计算

  • 若 T(n) 是常数，那么无脑简化为1
  • 若 T(n) 是多项式，比如 3n^2 + 5n + 3，我们只保留次数最高那一项，并且将其常数系数无脑改为1。

# 遍历

在所有的for循环里，判断语句都会比递增语句多执行一次。

function traverse(arr) {
    var len = arr.length  //1
    // for循环--执行n次
    for(var i=0;i<len;i++) { //1+(n+1)+n
        console.log(arr[i]) //n
    }
}

// 总的执行次数
// T(n)=1+n+1+(n+1)+n
// T(n)=3n+3
// 时间复杂度 O(n)

# n*n的二维数组的遍历

function traverse(arr) {
    // 1
    var outLen = arr.length

    for(var i=0;i<outLen;i++) {// 1+n+(n+1)
        // n
        var inLen = arr[i].length

        // n*(1+n+(n+1))
        for(var j=0;j<inLen;j++) {
            console.log(arr[i][j]) // n*n
        }
    }
}
//1+1+n+(n+1)+n

T(n)=3n^2+5n+3
// 时间复杂度 O(n^2)

遍历n维数组，需要n层循环，只需要关心最内层那个循环体被执行多少次就好

# 总结

  • 规模为n的一维数组遍历时，最内层的循环会执行n次，时间复杂度为O(n)
  • 规模为n*n的二维数组遍历时，最内层的循环会执行n*n次，其对应的时间复杂度为O(n^2)
  • n*m规模=>O(n*m)

# 常见时间复杂度

类型 时间复杂度
常数时间 O(1)
对数时间 O(logn)
线性时间 O(n)
线性对数时间 O(nlogn)
二次时间 O(n^2)
三次时间 O(n^3)
指数时间 O(2^n)

# 空间复杂度计算

对一个算法在运行过程中临时占用存储空间大小的量度，和时间复杂度相似，它是内存增长的趋势

常见的空间复杂度有 O(1)、O(n) 和 O(n^2)。

// len arr i
// O(1)
function traverse(arr) {
    var len = arr.length
    for(var i=0;i<len;i++) {
        console.log(arr[i])
    }
}

//O(n) 初始化一个规模为n的数组
function init(n) {
    var arr = []
    for(var i=0;i<n;i++) {
        arr[i] = i
    }
    return arr
}

//O(n^2) 初始化一个规模为n*n的数组

← 递归 →