算法复杂度

前言

算法复杂度分为时间复杂度和空间复杂度。

算法的复杂性体运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。

时间复杂度

是指执行算法所需要的计算工作量,指时间增长的趋势。

T(n) = O( f ( n ) )

  • 常用时间复杂度量级
  1. 常数阶O(1): 算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。

    int x = 0; 
    int y = 1; 
    int temp = x; 
    x = y ;
    y = temp;
    

    该程序段的执行时间是一个与问题规模n无关的常数

  2. 对数阶$O(logN)$由于计算机使用二进制的记数系统,对数常常以2为底(即 $ log_2n $,有时写作 $logn$ )。然而,由对数的换底公式,$log_an$ 和 $ log_bn$只有一个常数因子不同,这个因子在大O记法中被丢弃。因此记作 $ O(logn)$,而不论对数的底是多少,是对数时间算法的标准记法。

    典型的二分查找法:假如有32份试卷,你丢一次,还剩16份 ,丢两次,还剩下8 份,丢三次,就只剩下4份了,可以这么一直丢下去,丢到第五次,就只剩下一份了。而$log_2(32)=5 $。也就是我们一次丢一半,总要丢到只有一份的时候才能出结果,如果有n份,那么显然我们就有 $n/2^k =1 => l=log_2n $

  3. 线性阶O(n): 随着样本数量的增加,复杂度也随之线性增加

    for(int i = 1;i<=n;i++){
        x++;		//O(1+3N)=O(N)
    }
    
  4. 线性对数阶O(nlogN):

    比如对一堆带有序号的书进行排序。先选一本,然后把号码大于这本书的扔右边,小于这本书的扔左边。因为每本书都要比较一次,所以这么搞一次的复杂度是 O(n),那么快排需要我们搞多少次呢?这个又回到了二分查找的逻辑了,每次都把书堆一分为二,请问分多少次手里才能只剩下一本书呢?答案还是logn。而从代码的角度来说,在到达大小为一的数列之前,我们也是需要作logn次嵌套的调用。

  5. 方阶$O(n^2)$: 计算的复杂度随着样本个数的平方数增长

    在比如说构建一个网络,每个点都和其他的点相连。显然,每当我们增加一个点,其实就需要构建这个点和所有现存的点的连线,而现存的点的个数是n,所以每增加1,就需要增加n个连接,那么如果我们增加n个点呢,那这个连接的个数自然也就是 $n^2$ 量级了。

----------------TODO---------------

  • 立方阶 $O( n^3 )$

  • k次方阶 $O(n^k)$

  • 指数阶$ O(2^n)$

  • 阶乘 O( n!)

----------------TODO---------------

空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势。

S(n) = O( f ( n ) )

  • 常见的空间复杂度$O(1)、O(n)、O(n^2)$:
  1. O(1)

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

    int x = 0;
    int y = 0;
    x++;
    y++;
    

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

  2. O(n)

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

    上面这段代码中,new了一个数组出来,占用空间大小为n,后面的for循环只是给这个数组赋值并没有分配新的空间,因此这段代码的空间复杂度主要取决于 n 的大小。

  3. $O(n^2)$

    比如说二维数组...

更新时间:2020-09-22 00:39:37

本文由 阿俊 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://jinterest.cn/archives/ds-alg
最后更新:2020-09-22 00:39:37

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×