算法之空间复杂度以及评判算法的标准(Java)

//例如：给出一些整数n：3 1 2 5 4 9 7 2，其中
//有两个整数是重复的，要找出这两个重复地整数。
// 对于这个简单的需求，可以使用很多的思路类解决，其中最朴素的就是
//双重循环
//遍历整个数列，每遍历一个新的整数就开始回顾
// 之前遍历过的所有整数。
//即 第1步：遍历整数3，前面没有数字，所有无须回顾比较
//   第2步：遍历整数1，回顾前面的数字3，没有发现重复的数字
//   第3步：遍历整数2，回顾前面的数字3、1，没有发现重复的数字
//  ....
// 后续的步骤跟上面的相似，一直遍历到最后的整数2
// 发现和前的整数2重复
// 通过双重循环可以得到最终的结果但是并不是一个好的算法
// 为了提高运行速率，我们需要引入中间数据
/*
  当遍历整个数列时，每遍历一个整数时，每遍历一个整数，
  就把整数存储起来，起来像放到字典中一样。当遍历下一个整数时
  不必再慢慢向前回溯比较，而直接去“字典”中查找，看有没有对应的整数即可
  假如已经遍历的前7个整数，那么字典里面存储的信息为：
  key value
  3    1
  1    1
  2    1
  5    1
  4    1
  9    1
  7    1

具体问题需要具体分析。和时间复杂度类似
 空间复杂度也有几种不同的增长趋势。
 */
// 常见的空间复杂度有以下的几种情形。

    public static void main(String[] args) {


    }


    //1. 常量空间
// 当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)
// 例如下面程序
    public void fun1(int n) {
        int var = 3;

    }


    // 2. 线性空间
//当算法分配的空间是一个线性的集合(如数组)，并且结合的大小和输入规模n成正比时
//空间复杂度记作O(n),例如下面的程序
    public void fun2(int n) {
        int[] array = new int[n];

    }

    // 3. 二维空间
    /*
      当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比时
      空间复杂度记作为O(n^2)
      例如下面的程序
     */
    public void fun3(int n) {
        int[][] matrix = new int[n][n];
    }

    //4. 递归空间
    /*
     递归空间是一个比较特殊的场景，虽然递归代码中并没有
     明显式地声明变量和集合，但是计算机在执行程序的时候
     会专门分配一块内存，用来存储为“方法调用栈”

     “方法调用栈”包括进栈和出栈两个行为：
      当进入一个新方法时，执行入栈操作，把调用的方法和参数信息从栈中弹出
      当返回方法时，执行出栈操作，把调用的方法和参数信息从栈中弹出
      下面是一个标准的执行的递归程序：
     */

    public void fun4(int n) {
        if (n 

代码分析：假如初始传入参数值为n = ,那么方法fun4(参数n=5)的调用信息先入栈
                   method fun4
                     n      5
接下来递归调用相同方法，方法fun4(参数n=4)的调用信息入栈。
                   method    fun4
                      n        4
                   method      fun4
                      n         5
依次类推，递归越来越深，入栈的元素越来越多。
                     method    fun4
                       n        1
                     method     fun4
                       n        2
                     method     fun4
                       n         3
                       method     fun4
                       n         4
                        method     fun4
                       n         5
               当n = 1时，达到递归结束条件，执行return指令，方法近栈。
                  method     fun4
                       n        2
                     method     fun4
                       n         3
                       method     fun4
                       n         4
                        method     fun4
           服务器托管网            n         5
                   最终，“方法调用栈”的全部元素会--出栈
                    由上面”方法调用栈“的出入栈过程可以看出，执行递归操作
                    所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是现行的，
                    如果递归深度的深度为n，那么空间复杂度就是O(n)

人们之所以花大量的力气去评估算法的时间复杂度和空间复杂度，其根本

原因就是计算机的运行速度和空间资源是有限的。

就如一个大财主，基本不必为日常花销伤脑筋，而一个没多少积蓄

的普通人，则不得为日常花销精打细算。

对于计算机系统来说如此。虽然目前计算机的CPU处理速度不断飙升，

内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然

要精打细算，选择最有效的的利用方式。

双重循环的时间复杂度是O(n^2)，空间复杂度是O(1),这属于

牺牲空间来换取时间的情况。

相反，字典法的空间复杂度是O(n)，时间复杂度是O(n)，这属于牺牲空间

来换取时间的情况，在大多数情况的时候，时间复杂度是O(n)，这属于牺牲空间来换取时间的情况

在绝大多数的时候，时间复杂度更为重要些，宁可多分配一些空间，也要提升程序的执行速度

空间复杂度就离不开数据结构。