时间复杂度&空间复杂度

时间复杂度&空间复杂度

老说时间复杂度,空间复杂度,能不能简单描述一下?说人话!

空间复杂度

概念

Space Complexity,对一个算法在运行过程中临时占用存储度空间的度量,记做S(n)=O(f(n));

其实白话就是,一段程序运行需要分配的空间,我们用一个线性函数来描述它的变化趋势,我们把这个变化趋势整体就叫做这个算法的空间复杂度!

来看以下代码示例:

int a = 1;
a++;
int b = 2;
b+=1;
int c = a + b;

int n = 10;
int [] arr = new int[n];

int mi = 2;
int m = (int)Math.pow(n,mi);
int [] arr1 = new int[m];

那么上面一段代码的空间复杂度分别怎么表示呢?

可以看到因为a,b,c 三个变量都是加减操作,存储空间根据字节长度有关,它们的字节都是线性增长的,所以它的空间复杂度我们记做:
$$
S(n)=O(1)
$$
arr 数组分配的空间和它的初始长度n 相关,所以它的空间复杂度我们记做:
$$
S(n) = O(n);
$$
arr1 数组分配的空间和它的初始长度m 相关,而m 是n的mi次方即: m = n^mi

这里是mi为2, 则arr1的空间复杂度我们记做:
$$
S(n) = O(n^2)
$$

时间复杂度

概念

Time Complexity, 对一个算法运行时所需要消耗的时间的度量,记做:T(n) = O(f(n));

白话理解就是一个程序运行所需要的时间,我们并不是直接描述它占用时间的长短,而是从宏观上评估它的所消耗时间的一个趋势,而它的变化趋势我们也可以用各种线性函数来表示(即所写代码的执行次数和什么相关的函数),那这种线性函数的描述方式我们叫做时间复杂度;

来看以下代码示例:

O(1)

int count;
int i = 1;
int j = 2;
int k = 3;
count = i + j + k;

从上面代码我们可以看到,这段代码程序是自上向下执行一次的,那么对于这种只执行一次的代码时间复杂度我们记做:
$$
T(n)=O(1)
$$

O(log3n)

int n = 100;
int i = 1;
while(i<=n){
    i=3*i;
}

在上面代码中,while循环每次i都自增3倍,如果自增x次后i>n就退出循环了,也就是3的x次方时退出了循环,可以确定的是x次循环后i一定是一个大于n的某个值,在时间复杂度的考量中我们将此值忽略直接记做n,那么3的x次方等于n,成对数即是x = log(3)(n)。说明这段代码的执行次数x 是个对数函数,对应的时间复杂度我们记做:
$$
T(n) = O(log_3n)
$$

O(n)

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

上面代码是一个简单的for循环,那么很明显它的执行次数和n的大小有关,我们将这种for循环的时间复杂度记做:
$$
T(n)=O(n)
$$

O(nlogN)

int n = 1000;
int j;
for(int i = 0;i<n;i++){
    j = 1;
    while(j<n){
        j = 2*j;
    }
}

在上面一段代码中,我们可以看到for循环中每次都对i 重新做了赋值操作;

保证 while 循环每次都能执行log(2)(n)次,那么它总的执行次数就是n*log(2)(n), 那么这个时候决定执行的次数的关键就在于n的大小了,至于是2倍还是几倍的增长变得不再那么重要,我们可以忽略(极限思维)统一记做N。那么它的时间复杂度我们就记做:
$$
T(n)= O(nlogN)
$$

O(n^k)

int n = 100;
for(int i = 0;i<n;i++){

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

        for(int k = 0;k<n;k++){

        }
    }
}

上面代码三个for循环,明显执行了n* n * n即n^3

它的时间复杂度我们记做:
$$
T(n) = O(n^3)
$$

O(2^n),O(n!)

实际上幂指数增长和穷举,基本没有见过这样的程序,你想什么样的算法会是指数性的和穷举型的?(网络攻击?这两个不常见,了解即可)

常见时间复杂度函数图

从图中我们可以看到趋势越陡的函数时间复杂度肯定大,那么以上的时间复杂度从大到小依次是:
2^n > (n^3)/3 > 5n^2 > 500log(2)(n) > 100n

那么我们可以推断出常见的时间时间复杂度从大到小依次是:
$$
O(2n) > O(n3)>O(n^2)>O(nlog_2n)>O(n)>O(log_2n)>O(1)
$$

时间复杂度越大,算法的执行效率越低!

参考文章

最后关于时间复杂度的更形象的总结,推荐篇博客 :一套图 搞懂“时间复杂度”

关于8大排序算法时间复杂度稳定性的总结,推荐博客:八大排序算法、稳定性及时间复杂度

小结:我们学习了解任何知识,一定不能死啃概念,要试着把自己不能理解的东西抽象成自己可以理解的东西!很多东西我们不能理解,是很多时候是有些技术类文章不说人话。有些也是自己眼界不够,而有些则是说的人能力不够还无法做到通俗易懂的讲解出来!如果你能做到通俗易懂的讲解出来,那说明你已经掌握了!