vlambda博客
学习文章列表

【学习一】数据结构与算法——算法复杂度

数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?这里就要用到我们今天要讲的内容:时间、空间复杂度分析。


其实,只要讲到数据结构与算法,就一定离不开时间、空间复杂度分析。而且,我个人认为,复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半。



【学习一】数据结构与算法——算法复杂度

【学习一】数据结构与算法——算法复杂度

【学习一】数据结构与算法——算法复杂度

【学习一】数据结构与算法——算法复杂度

【学习一】数据结构与算法——算法复杂度



空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {

  int i = 0;

  int[] a = new int[n];

  for (i; i <n; ++i) {

    a[i] = i * i;

  }

  for (i = n-1; i >= 0; --i) {

    print out a[i]

  }

}


跟时间复杂度分析一样,我们可以看到,第 2 行代码中,我们申请了一个空间存储变量 i,但是它是常量阶的,跟数据规模 n 没有关系,所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是 O(n)。


我们常见的空间复杂度就是 O(1)、O(n)、O(n2 ),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。