对于时间复杂度和空间复杂度的理解

时间: | 分类: 其他分类

一开始对于时间复杂度和空间复杂度的理解还是有些晕,虽然知道是和运行次数有关系,但是似乎又有些不同。看了某个培训机构的网课,有了些新的理解,作为个人的记录参考一下,如有理解错误欢迎指正!

2018-12-11

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

很明显这个运算次数是n,时间复杂度是O(n)

void func(int n){
    for(int i=0;i<n;i++){
        System.out.println(i);
    }
    for(int j=0;j<10000000;j++){
        //do nothing;
    }
}

一开始不太理解,照理说每一次运算都要循环1E7次,那复杂度应该是O(10000000+n)才对呀?
其实还有一个时间频度的概念,即语句执行的次数,在时间频度里,这个算法就是T(10000000+n)。
在n等于无穷大的时候,这个常数(10000000)并不会对算法造成多大影响,假设n=100000000000000,那么这一点点常数并不会影响整体的复杂度,处理器执行的速度不一样,对于奔腾,可能需要5秒才能执行完1000万次,对于I9,可能0.5秒就执行完了,那么运算的次数实际取决于n,而不是常数。时间频度关注的是执行次数,而时间复杂度关注的是问题的规模,和常数是无关的(因为常数并不影响问题的规模,复杂度关心的是规模,而不是运行时间
T(10000000*n)==O(n)
上面这个时间复杂度其实等价于:

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

虽然时间频度是T(10000000*n),但是当n=1时,运算10000000次,当n=2时,运行20000000次,可以看出,具体的运算次数也是和n相关的线性的变化,随着n增加而导致的线性增长并不会被常数影响。所以时间复杂度包含常数没有意义,因为复杂度不关心运行次数(运行时间),关心的是规模,这个规模取决于n的变化而变化,所以这个算法是O(n)的时间复杂度

另外一题:

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

虽然看起来进行了两次循环,但是实际上运算的次数依然是线性增长,所以常数是多少都可以忽略。

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

这一题的时间频度是T(n²),当n=1,运算2次,当n=2,运算4次,当n=3,运算9次,这个^2不再是常数,问题的规模随着n的增加而指数增长。

void func(int n){
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){//注意这里int j =i,j的初始值与外层循环有关
            System.out.println(i);
        }
    }
}

看起来似乎有点奇怪。运算次数是(1+2+3+....+n-1+n)n,即(n+1)n/2,这是时间频度,由于常数不随n变化而变化,所以时间复杂度可从时间维度简化得n*n,即n²。

void func(int n){
    for(int i=1;i<n;i*=2){//注意i的自增
        System.out.println(i);
    }
}

设n为8,运算结果为

2 4 8

由于n每次都x2,那么实际运算次数是T(log2 8)(以2为底),由于2也是常量,则简化后时间复杂度为O(log n)

而空间复杂度也是类似的概念

void func(int n){
    int a,b,c,d,e,f,g,h,j,k,l,m,n,o,p,q,r,s,t;//声明了许多个变量
    for(int i=1;i<n;i++){
        System.out.println(i);
    }
}

看起来声明了很多个变量,但是实际上这些变量占用的空间并不随n的变化而变化,因此也可以当作常数处理,所以这个的空间复杂度是O(n)。

void func(int n){
    int[] arr = new int[n];//以n作为数组空间初始化的值
    for(int i=1;i<n;i++){
        System.out.println(i);
    }
}

而这个方法可以看出,数组的大小取决于n,那么空间复杂度则为O(n)

空间复杂度同理不再赘述。

时间复杂度一般求最坏的时间复杂度,对于平均时间复杂度

  1. 难计算
  2. 大部分算法的平均情况和最坏时间复杂度是一样的。

所以一般讨论的时间复杂度都是最坏的时间复杂度

复杂度的三种符号:

O 时间复杂度的上界(最坏情况)
Ω 时间复杂度的下界(最好情况)
Θ 时间复杂度的精确阶(最好和最坏都是一个阶)

(以下是oi大佬ice姐姐对于时间复杂度的看法,新标签打开可看大图qwq)


算法 时间/空间复杂度



白咲美绘瑠's blog