• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构还债——时间复杂度与空间复杂度

开发技术 开发技术 6天前 3次浏览

时间复杂度

由于语句执行的次数就可以代表程序执行的时间,空间复杂度时间复杂度就是程序在执行过程中语句的执行次数

数据结构还债——时间复杂度与空间复杂度

上面的方法中只有一条语句所以执行次数为1,所以我们可以看作执行时间T1(n) = 1.

数据结构还债——时间复杂度与空间复杂度

上面的方法的语句中有4个语句,所以执行完的次数为4,则T2(n) = 4.

数据结构还债——时间复杂度与空间复杂度

那么上面的方法中,执行了多少次呢,由于i < n所以一共执行了n次,则T3(n) = n.

数据结构还债——时间复杂度与空间复杂度

上面的方法中i++变为了i = i + 0.5,因此整体执行次数也比之前的多了一倍,则T4(n) = 2n.

数据结构还债——时间复杂度与空间复杂度

上面的方法中,循环中又嵌套了循环,每个循环执行n次,所以一共执行了n*n次,则
$$
T5(n) = n^2.
$$
数据结构还债——时间复杂度与空间复杂度

上面的程序,i每次增加两倍,则需要的次数就变成了
$$
T6(n) = log^2n
$$

总结

  • T1与T2这种类型,方法中有多少个句子就执行多少次的,可以认为时间复杂度都为O(n) = 1。因为都是常数,可以对这些常数进行简化,都看作1
  • T3与T4这两种类型,方法中的句字由于循环或者其他结构导致执行了n次以上,也就是T(n) = n、T(n) = 2n或者T(n) = 2n + 3,这种类型的,一般将常数项与n的系数都进行简化,化简为O(n) = n
  • T5中的执行次数为n2,诸如此类的还有n2 + 1、3n^2 + n,这些类型都可以简化为O(n) = n^2
  • T6与T5相似,可以将底数直接省略简化,则O(n) = logn

为什么简化?

时间复杂度只是一个大概的数字,并不是精确的,所以比如n和n + 1,1比n小很多很多,当n足够大的时候,1就可以忽略了,同理n2+3n中,3n与n2,在n足够大的时候,都是可以忽略不计的

空间复杂度

与时间复杂度相似,也用O(n)表示,只不过时间复杂度衡量的不是执行次数,而是程序执行时所占用的内存空间

void Demo(){
    int i = 0;
}

上面这个程序中,仅为i申请了一个空间的内存

void Demo(){
    int i = 0;
    int j = 1;
    int m = 2;
}

上面这个程序中,为i、j、m一共申请了三个空间的内容,与时间复杂度相似,这种类型的空间复杂度为O(n) = 1

void Demo(int n){
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
        arr[i] = i;
    }
}

上面这个程序为给一个数组初始化的过程,且数组长度为n,则申请到了n个空间的内存,假如数组长度为2n,则就是2n个空间的内存,所以这种类型的空间复杂度O(n) = n.

时间复杂度的n^2、logn与时间复杂度类似,但不常用,因此不再举例

总结

  • 空间复杂度与时间复杂度,除衡量的标准不一样,其计算方式,简化方式,都与时间复杂度一样
  • 在有递归的方法中,因为要不停的递归创建方法栈空间,所以递归的时间复杂度至少为n
  • 时间复杂度与空间复杂度很难两全,往往都是通过时间换空间,或者通过空间换时间

程序员灯塔
转载请注明原文链接:数据结构还债——时间复杂度与空间复杂度
喜欢 (0)