Algorithms_入门基础_时间复杂度&空间复杂度

算法的基本特征 & 设计原则

基本特征

• 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  
• 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出。
  
• 可行性：一个算法是可行的，即算法中描述的操作都是吋以逋过已经实现的基本运算执行有限次来实现的。
  
• 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
  
• 输出：一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。
  

设计原则

通常设计一个“好”的算法应考虑达到以下目标：

• 正确性：算法应当能够正确地解决求解问题。
  
• 可读性：算法应当具有良好的可读性，以助于人们理解。
  
• 健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
  
• 效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
  

评价算法的两个重要指标

• 时间复杂度 ： 运行一个程序所花费的时间 O()
• 空间复杂度: 空间复杂度也不是用来计算程序实际占用的空间的。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，通常用 S(n) 来定义。

https://zhuanlan.zhihu.com/p/50479555

时间复杂度

定义

运行一个程序所花费的时间 。

举个例子 ,如何测试我们的程序性能？ 性能测试之类的对吧-----> 主机的性能不同，数据的准确性和数据量等等 ，都会对我们的结果产生影响。

作为开发人员如何评估下呢？ --> 我们需要评估下自己的代码，就是 时间复杂度，寻求一个最优的组合，做到心中有数。

表示方法

大O表示法 ，比如我们常见的 O(1)、O(N) 、O(nlogn)、O(n^2）、O(n+1）、O(n!)等等

如何计算时间复杂度

算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为“频度”）。次数越少，算法的时间复杂度越低。

举个例子：

a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }

上边这个例子中，a 代码的运行了 1 次，b 代码的运行了 n 次，c 代码运行了 n*n 次。

所以上边的例子而言，a 的时间复杂度为O(1)，b 的时间复杂度为O(n)，c 的时间复杂度为为O(n^2)。

如果a、b、c组成一段程序，那么算法的时间复杂度为O(n^2+n+1)。但这么表示是不对的，还需要对n^2+n+1进行简化

简化的过程总结为3步：

• 去掉运行时间中的所有加法常数。（例如 n^2+n+1，直接变为 n^2+n）
• 只保留最高项。（n^2+n 变成 n^2）
• 如果最高项存在但是系数不是1，去掉系数。（n^2 系数为 1）

所以，最终a、b和c合并而成的代码的时间复杂度为O(n^2)

几种常见的时间复杂度

可查考 维基百科 ： 时间复杂度

这里我们挑几个常用的来 解释一下

• 常数阶：O(1)
• 对数阶：O(logN)
• 线性阶：O(n)
• 线性对数阶：O(nlogN)
• 平方阶：O(n^2)
• 立方阶：O(n^3)
• K次方阶：O(n^k)
• 指数阶：O(2^n)

上面从上至下时间复杂度越来越大。 执行效率越来越低。

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

如何分析时间复杂度

• 最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
• 平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
• 最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

常数 O(1)

public class BigO {
    public static void main(String[] args) {
        int a = 1 ;// 1.运行几次？ 
        for (int i = 0; i < 5; i++) { // 3.运行几次？
            a = a + 1 ;  // 2.运行几次？
        }
    }
}

来看下

public static void main(String[] args) {
        int a = 1 ;// 1.运行几次？ ----> n=1次 ， T(n) = O(1)
        for (int i = 0; i < 5; i++) { // 3.运行几次？ ---> n=6次  在第6次的时候跳出循环 运行了(0,1,2,3,4,5)
            a = a + 1 ;  // 2.运行几次？ ---> n=5次  ，T(n)是?  O(5) ?  O(1) ? O(n)? ---> O(1)
        }
    }

上面的代码消耗的时间并不随着某个变量的增长而增长，运行的次数固定，那么无论这个类的代码有多长，即使有成千上万行，都可以用O(1)来表示它的时间复杂度。

对数阶O(logn)

来看个代码 ，算下这个的时间复杂度是 ？

// n 未知 
  int i = 1 ;
  while( i <= n){
       i = i * 2;   
    }

推演下：

n未知

i的值：1,2 4 8 16 32,=》2^0,2^1,2^2,2^3,.....2^n

===> 2^x=n ======>求出x就是我们运行的次数 => x=log2n =>计算机忽略掉常数 => x = logn =>O(logn)

while( i <= n){
       i = i * 3;   //O(logn)
    }

同样的，上面的 虽然是乘以3 ，但是也是O(logn)， 常数忽略

需要注意的是，如果n是个常数，那么时间复杂度就是O(1)了。

经典的二分查找算法时间复杂度就是 O(logn)

假设总共有n个元素，那么每次查找的区间大小就是n，n/2，n/4，…，n/2^k，其中k是循环的次数。

在最坏情况下是在排除到只剩下最后一个值之后得到结果，即n/2^k = 1 。

即n/2^k=1，=====> 2^k=n ===⇒ 可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表O(logn)

public static int biSearch(int[] array,int a){
        int lo = 0;
        int hi = array.length-1;
        int mid;
        while(lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if(array[mid] == a) {
                return mid + 1;
            }else if(array[mid] < a) {
                lo = mid + 1;
            }else{
                hi = mid - 1;
            }
        }
        return -1;
    }

线性阶O(n)

n未知

for(i = 0 ; i < n;i++){
  a = a +1;     
}

上述代码的时间复杂度呢？

运行了多少次？ 随着n的增长，这个运行时间是线性增长的 -----> O(n) n一定是一个未知的。

需要注意的是，如果n是个常数，那么时间复杂度就是O(1)了。

线性对数阶O(nlogN)

理解了 线性对数阶O(logn) ， 再来看 O(nlogN) 就很容易理解了—> 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN) = O(nlogN).

n未知

把 O(logn)的代码稍微一改,外面套一层循环，就成了一个O(nlogN)了

int i = 1;
  for(int j = 0 ; j < n ;j++){ // 循环n次 
    while ( i <= n){
      i = i * 2; ---> O(logn)
    }
  }

两层循环， 乘法运算， n* O(logn) = O(nlogN) .

平方阶O(n²)

n未知

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

for(i = 0 ; i < n;i++){ // 乘法 n次
      for(int j = 0 ; j < n ;j ++){   //n次
        a = a +1;     //运行了多少次？   O(n^2)
      }
    }

如果将其中一层循环的n改成m，比如：

for(i = 0 ; i < m;i++){ // 乘法 m次
      for(int j = 0 ; j < n ;j ++){   //n次
        a = a +1;     //运行了多少次？   O(m*n)
      }
    }

那它的时间复杂度就变成了 O(m*n)

再来看下面的时间复杂度 ， 第二层循环 令 j = i

for(i = 0 ; i < n;i++){ // 乘法 n次
  for(int j = i ; j < n ;j ++){   //n次 
    a = a +1;     //运行了多少次？ n*(n+1)/2 => O(n^2); => (n^2+n)/2 => 注意有个规律，有加减法的时候，找次数最高的那个
    }
  }

分析一下

第一层的循 次数是确定的 O(n) n次，1 2 3 4 。。。n

那第二层的循环：

i=n 第二层循环运行1次

i=n-1 第二层循环运行2次

…

…

…

i=1 第二层循环运行n次

来算下第二层循环总共运行 1+2+3+……+n （等差数列求和嘛） = n*(n+1)/2 ===> 忽略所有常数=> 时间复杂度为 O(n^2)

注意有个规律，有加减法的时候，找次数最高的那个

立方阶O(n³)、K次方阶O(n^k)

这个类比 O(n^2)理解即可 O(n³)相当于三层n循环， O(n^k)相当于k层n循环 .

时间复杂度排序

我们优化的指标当然是时间复杂度越少也好，向O（1）靠拢 。

通常 常数阶：O(1)>对数阶：O(logN)> 线性阶：O(n）>线性对数阶：O(nlogN) 效果都是很好的。几乎优化的空间不是很大

两条规则

在分析一个程序的时间复杂性时，有以下两条规则：

a) 加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

b) 乘法规则

T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n) )

常见的渐近时间复杂度有：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

空间复杂度

概述

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。反映的是一个趋势，通常用 S(n) 来定义

一个算法在计算机存储器上所占用的存储空间，包括

• 存储算法本身所占用的存储空间 ----Space Complexity不考虑在内
• 算法的输入输出数据所占用的存储空间 ----Space Complexity不考虑在内
• 算法在运行过程中临时占用的存储空间 <------ 考量这个

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。

存储算法本身所占用的存储空间与算法编写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

算法在运行过程中临时占用的存储空间随算法的不同而异，

• 有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法；
• 有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元.

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

O(1)

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

举个例子

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

变量 a、b 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

变量所分配的空间都随着处理数据量变化而变化 ，随着变量的增大而增大。

举个例子

j = 0 ;
int[] a = new int[b];
for(i=1; i<=b; ++i)
{
   j = i;
   j++;
}

分析一下： new了一个数组，需要开辟对应的内存空间， 数组长度为1，和数组长度为1个亿，占用的临时空间肯定是不同的。

算一下哈 1 int = 4字节 ，

我们开辟数组长度为10的int数组 ， 10 * 4Byte = 40字节

开辟1亿个int ,那就是1亿 * 4Byte / 1024 /1024 = 381m

可见， 一个40字节，一个381m ，空间复杂度随着b的增长而增长

还有一点：开辟完这个数组后，后面的代码，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看int[] a = new int[b]即可，即 S(n) = O(n) 。

常见排序算法的复杂度