Java教程

时间复杂度和空间复杂度

本文主要是介绍时间复杂度和空间复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

时间复杂度

简单理解,为了某种运算而花费的时间,使用大写O表示。一般来讲,时间是一个不太容易计量的维度,而为了计算时间复杂度,通常会估计算法的操作单元数量,而假定每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量一般来讲成正比,最多相差一个常量系数。一般来讲,常见时间复杂度有以下几种:

  1. 常数阶O(1):时间与数据规模无关,如交换两个变量值

    int i=1,j=2,k
    k=i;i=j;j=k;
    
  2. 线性阶O(n):时间和数据规模呈线性,可以理解为n的1次方,如单循环里的操作

    for(i=1;i<=n;i++){
        do();
    }
    
  3. k次方阶O(nk):执行次数是数量的k次方,如多重循环,以下为2次方阶实例

    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            do();
        }
    }
    
  4. 指数阶O(2n ):随着n的上升,运算次数呈指数增长

  5. 对数阶O(log2n):执行次数呈对数缩减

  6. 线性对数阶O(nlog2n):在对数阶的基础上,进行线性n倍乘积

时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<...<Ο(nk)<Ο( 2n)<Ο(n!)

空间复杂度

与时间复杂度类似,空间复杂度是对一个算法在运行过程中占用内存空间大小的度量。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的辅助空间。而空间复杂度主要指的是这部分空间的量级。

  • 固定空间:主要包括指令空间、常量、简单变量等所占的空间,这部分空间的大小与运算的数据多少无关,属于静态空间。
  • 可变空间:主要包括运行期间动态分配的临时空间,以及递归栈所需的空间等,这部分的空间大小与算法有很大关系。

for(i=1;i<=n;){
i=2^i;
do();
}
for(i=1;i<=2^n;i++){
for(j=1;j<=n;j++){
do();
}
}

同样,空间复杂度也用大写O表示,相比时间复杂度场景相对简单,常见级别为O(1)和O(n),以数组逆序为例,两种不同算法对复杂度影响如下:

  1. O(1):常数阶,所占空间和数据量大小无关。

    //定义前后指针,和一个临时变量,往中间移动
    //无论a多大,占据的临时空间只有一个temp
    int[] a={1,2,3,4,5};
    int i=0,j=a.length‐1;
    while (i<=j){
        int temp = a[i];
        a[i]=a[j];
        a[j]=temp;
        i++;
        j‐‐;
    }
    
  2. O(n):线性阶,与数据量大小呈线性关系

    //定义一个和a同等大小的数组b,与运算量a的大小呈线性关系
    //给b赋值时,倒序取a
    int[] a={1,2,3,4,5};
    int[] b=new int[a.length];
    for (int i = 0; i < a.length; i++) {
        b[i]=a[a.length‐1‐i];
    }
    

总结

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。时间复杂度低可能借助占用大的存储空间来弥补,反之,某个算法所占据空间小,那么可能就需要占用更多的运算时间。两者往往需要达到一种权衡。

在特定环境下的业务,还需要综合考虑算法的各项性能,如使用频率,数据量的大小,所用的开发语言,运行的机器系统等。两者兼顾权衡利弊才能设计出最适合当前场景的算法。

这篇关于时间复杂度和空间复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!