算法的时间复杂度和空间复杂度(js版)

一、复杂度的表示方式

大O表示法，其中T代表的是算法需要执行的总时间，S表示的是算法需要的总空间

f(n)表示的是代码执行的总次数

T(n) = O(f(n))

S(n) = O(f(n))

举个例子

function go(n) {

    var item = 0; //这里执行了一次

    for (var i = 0; i < n; i++) { // 这里执行了n次

        for (var j = 0; j < n; j++) { // 这里执行了n*n次

            item = item +i +j; // 这里执行了n*n次

        }

    }

    

    return item; // 这里执行了一次

}

因此上面这段代码是 1+n+n*n*2+1=2+n+2n²

也就是说 T(n) = O(f(2 + n + 2n²))

但是由于时间复杂度参考的是代码执行时间的趋势，因此当n规模比较大的时候，常量起不到决定性的作用，因此这个时候我们忽略这些常量。

因此这里的例子，只看最大量级的循环就可以了，它的时间复杂度是 T(n) = O(n²)

二、时间复杂度

a.时间复杂度的定义

首先，时间复杂度不代表代码执行的时间，算法的时间复杂度说的是一个算法的执行时间根据规模增长的一个趋势，而并不是代码执行的具体时间

b.几种常见的时间复杂度

1. O(n)

for (var i = 0; i < n; i++) {

    sum += i;

}

这个比较容易理解，这段代码的执行时间完全由N来控制，所以说T(n) = O(n)

2. O(1)

function total(n) {

    console.log('hello')

}

无论怎样，这段函数不受任何参数影响，代码走一遍就完了，这种代码的时间复杂度用 T(n) = O(1)

3. O(n²)

之前介绍的两层循环的代码，它的时间复杂度就属性 O(n²)

另外，再举个多块代码的情况下的时间复杂度计算方式

function go(i) {

    var sum = 0;

    for (var j = 0; j < i; j++) {

        sum += i;

    }

    

    return sum;

}

 

function main(n) {

    var res = 0;

    for (var i = 0; i < n; i++) {

        res = res + go(i); // 关注这里

    }

}

在上边的代码中第二段代码里调用了第一段代码，

第一段代码go: (1+ n)

第二段代码main: (1 + n*go) = (1 + n + n * n)

因此，最后的时间复杂度是 T(n) = O(n²)

c.多块代码的时间复杂度

上边举例说明的 T(n) = O(n²)，是一个函数在另一个函数里边被调用，这种情况下是把两个函数的时间复杂度相乘

还有另外一种情况，就是在一个函数里面有多块代码，但是并没有相互调用，在这样的情况下，我们只需要取复杂度最大的代码块就可以了

举个栗子

function go(n) {

    for (var i = 0; i < n; i++) {

        for (var j = 0; j < n; j++) {

            console.log(1);

        }

    }

    

    for (var i = 0; i < n; i++) {

        console.log(2);

    }

}

上边这块代码，第一块代码有两层循循环，它的复杂度是 n²；第二块代码，它的复杂度是 n

那么在这种情况下，当 n 接近无限大的时候，n 对整块代码的时间复杂度起不到决定性作用，因此在这里整块代码的复杂度就取起决定性作用的 n²

d.对数阶和相加情况

var i = 1;

while (i < n) {

    i = i * 10;

}

在上面这段代码中，可以看到while里面，判断条件i每次被*10，所以导致最后循环的次数并不是n次，通过计算这个代码的时间复杂度是 10 ^ x = n -> x = lgn

所以得出结论时间复杂度是 T(n) = O(logn)

e.其他情况

另外，还有的情况是通过改变变量会增加循环次数的，同理是增加了时间复杂度

还时间复杂度相加

function go(m, n) {

    for (var i = 0; i < n; i++) {

        console.log(1);

    }

    

    for (var j = 0; j < m; j++) {

        console.log(2);

    }

}

上面的代码，代码里面有两个循环，但是我们无法判断n和m到底哪个大，因此在这种情况下代码的时间复杂度是 O(m+n)

三、空间复杂度

a.空间复杂度的定义

时间复杂看的是代码的执行时间的趋势，那么同理的，空间复杂度就是指占用内存的趋势

b.常见的空间复杂度

空间复杂度没有时间复杂度那么复杂，常见的就是几种

因为一般大家不会一直循环着声明变量

1. O(1)

var a = 1;

var b = 2;

var c = 3;

2.O(n)

var arr = Array(n);

上面代码中创建了一个n长度的数组，数组的长度(内存开销)取决于n，因此空间复杂度是 O(n)

3.O(n²)

var arr = [];

for (vra i = 0; i < n; i++) {

    arr[i] = [];

    for (var j = 0; j < n; j++) {

        arr[i][j] = j;

    }

}

四、复杂度的优化

各个复杂度的曲线图

举个优化的例子

function go(n) {

    var total = 0;

    for (vra i = 1; i <= n; i++) {

        total+= i;

    }

    return total;

}

 

function go2(n) {

    return  (1 + n) * n / 2;

}

 

go(1000)

go2(1000)

比较这两个相同功能的函数的运算用时；可以体会到数学在优化算法时的重要性

另外，再举个斐波那契的栗子

斐波那契: 就是从第三项开始依次等于前两项的和

function Fibonacci(n) {

    if (n <= 1) {

        return n;

    } else {

        return Fibonacci(n - 1) + Fibonacci(n - 2);

    }

}

 

Fibonacci(10)

算法的时间复杂度和空间复杂度(js版)

推荐阅读