README

概念

程序 = 数据结构+ 算法

算法复杂度

算法的复杂性体现在运行该算法时计算机所需要的资源多少上 ，计算机资源最重要的是时间和空间（寄存器）资源，因此复杂度分为时间和空间复杂度

时间复杂度

是指执行算法所需要的计算工作量，指时间增长的趋势。T(n) = O( f ( n ) )

• 常用时间复杂度量级：

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

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

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

  2. 对数阶 ：由于计算机使用二进制的记数系统，对数常常以2为底（即 ，有时写作 ）。然而，由对数的换底公式， 和 只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作 ，而不论对数的底是多少，是对数时间算法的标准记法。 典型的二分查找法：假如有32份试卷，你丢一次，还剩16份 ，丢两次，还剩下8 份，丢三次，就只剩下4份了，可以这么一直丢下去，丢到第五次，就只剩下一份了。而。也就是我们一次丢一半，总要丢到只有一份的时候才能出结果，如果有n份，那么显然我们就有

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

     for(int i = 1;i<=n;i++){
         x++;    //O(1+3N)=O(N)
     }
     

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

  5. 方阶： 计算的复杂度随着样本个数的平方数增长 在比如说构建一个网络，每个点都和其他的点相连。显然，每当我们增加一个点，其实就需要构建这个点和所有现存的点的连线，而现存的点的个数是n，所以每增加1，就需要增加n个连接，那么如果我们增加n个点呢，那这个连接的个数自然也就是 量级了。

  6. TODO

     • 立方阶
     • k次方阶
     • 指数阶
     • 阶乘 O( n!)

空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势。S(n) = O( f ( n ) )

• 常见的空间复杂度、、:

  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. 比如说二维数组...

参考-JAVA全栈知识体系 (opens new window)