抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

算法的时间与空间复杂度

wuxuan.chai
算法

发布于：2021年1月22日
次浏览

算法的时间与空间复杂度

在日常开发过程中，衡量算法的性能，一般都是通过时间复杂度和空间复杂度两个维度去比较，本文就是梳理一下我们是如何计算时间复杂度和空间复杂度的。

时间复杂度

时间复杂度：指运行当前算法所消耗的时间，我们通常用【时间复杂度】来描述。

说到时间复杂度，我们第一时间想到的肯定是，算法从执行开始到执行结束所使用的时间。这么想固然是对的，但是仔细品，还是有弊端的。不同的机器运行相同的代码，时间会大不一样，取决于机器的CPU的执行运算的效率。如果机器相同，资源对等的情况下，我们考虑的可能就是代码层面的一些问题就会多一些，此时时间复杂度就是一个重要的评判标准。

一般时间复杂度分为：O(1)、O(n)、O(mlogn)、O(nm)

O(1)

1
2
3
4
5
public void o1(){
    int i = 10;
    i+=1;
    System.out.println(i);
}

O(1)的时间复杂度表示，无论代码执行多少行，只要没有循环结构，代码的时间复杂度都为O(1)。如上述代码，他执行的消耗时间和某个变量的增长是没有关系的，时间复杂度始终为O(1)。

O(n)

1
2
3
4
5
6
7
public void On(){
    int n = 10;

    for (int i = 0; i < n; i++) {
        System.out.println(n);
    }
}

O(n)的时间复杂度表示，当n的变化为10时，循环会执行十次，即时间复杂度时随着n的变化而线性变化的。

O(log n)

1
2
3
4
5
6
7
public void logn() {
    int i = 10;
    int j = 0;
    while (j < i) {
        j *= 2; 
    }
}

在上述例子中，每次循环中，j的值都会乘以2(可以认为n)，所以当循环m次后j的值就大于i了，循环就退出了，因此时间复杂度就为 lognm，所以复杂度一般简化为log n

O(nm)

1
2
3
4
5
6
7
for (int i = 0; i < n; i++) {
    for (int i1 = 0; i1 < n; i1++) {
        j = i;
        j++;
    }
}

在上述中的例子中，嵌套了两层的n循环，他的时间复杂度就为O(n*n), 即为O(n2)，如果有m层嵌套，那么时间复杂度为O(nm)

如果上述例子中，如果嵌套的循环时间复杂度为O(m),那么整体时间复杂为O(n*m)。

空间复杂度

空间复杂度是对一个算法在运行的过程中占用存储空间的一个度量指标，同时反应占用空间的一个趋势。

空间复杂度比较常用的有，O(1),O(n),O(n2)

O(1)

如果程序运行所需的临时空间不随着某个变量的变化而变化，那么算法的空间复杂度为一个常量

1
2
3
4
5
int i = 1;
int j = 1;
++ i;
j ++;
int m = j + i;

如上述的描述，执行所需的空间和i、j、m没有关系，所以他的空间复杂度为O(1)

O(n)

1
2
3
4
5
int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = i;
}

上述的例子中，数组a的空间和n的值成线性关系，即n有多大，数组就有多长，所以内存空间和n是成线性关系，所以空间复杂度为O(n)

O(nm)

1
2
3
4
5
6
7
int[] a = new int[n];
for (int i = 0; i < n; i++) {
    for (int ii = 0; i < n; i++) {
        a[i] = ii;
    }
}

上述例子中，双层循环中数组的长度和n、以及循环的嵌套层m数有关，所以内存空间和n、m的关系为nm,其空间复杂度为：O(nm)

总结

这里值是罗列基本的概念，具体的算法复杂度计算大致可以参考这个思路去推断。可能存在误解，后续学习再做改正。

相关文章
GreenPlum的百分位数的实现Java的位运算

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://cha1yi.github.io/dist/2021/01/22/%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E4%B8%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/

更新于：2021年1月27日

算法

算法
次浏览

字数：993字

时长：3分钟

评论