[数据结构与算法]03 计算时间和空间复杂度

以你之姓@ 2023-05-29 03:43 9阅读 0赞

学习数据结构与算法的时候,避不开的一个知识点就是:时间复杂度和空间复杂度分析.

为什么需要复杂度分析?  
一段代码我写好了,直接上手跑一遍,不就知道算法执行的时间和占用的内存大小了,为什么还要做分析呢?而且直接跑一遍得到的数据,准确的不能再准确了.  
因为直接跑一遍得到算法执行的时间和占用的内存大小,有一定的局限性.  
第一,同样一段代码,把它拿到 90 年代的笔记本上面执行,和拿到现在的笔记本上面执行,得到的时间是不一样的,所以直接拿来运行的代码,它的准确度真的够准确嘛?  
第二,如果数据量不够多,直接运行程序得到的结果可能有失其准确性.比如,对于小规模的数据排序,插入排序可能会比快速排序更快.  
对于计算时间和空间复杂度,一般是采用大 O 表示法来表示.

时间复杂度计算:  
什么是时间复杂度呢?是指执行当前算法所消耗的时间.  
常见的几种时间复杂度:O(1),O( l o g 2 n log\_2 n log2n),O(n),O( n 2 n^2 n2),O( 2 n 2^n 2n),O(n!)  
先来看一段简单的代码:

int n=1000;
    System.out.println("Hi, your input is:"+n);
    System.out.println("Hey, your code is:"+n);
    System.out.println("Hello, your verification code is:"+n);

先别往下看,你觉得这段代码的时间复杂度是多少?  
是 O(1) 对吧?因为这段代码都是常量级的执行时间,所以对于时间复杂度来说,它的复杂度为 O(1).  
请注意: O(1) 并不是指执行了一行代码,上面的程序执行了 3 行代码,它的时间复杂度也是 O(1).只要代码的执行时间不随 n 的增大而增长,那时间复杂度就都记为 O(1).一般情况下,只要程序中不存在循环语句,递归语句,就算是有上万行的代码,时间复杂度也是 O(1).  
来看另外一段代码:

for(int i=1;i<=n;i++){ 
      System.out.println("Hello, your verification code is:"+i);
    }

你觉得这段代码的时间复杂度是多少?  
先来分析一下,这段代码执行了 n 次, 所以它的时间复杂度为 O(n).  
如果是这样呢:

for(int i=1;i<=n;i++){ 
      for(int j=1;j<=i;j++){ 
        System.out.println("Hello, your verification code is:"+i+"and"+j);
      }
    }

这段代码的时间复杂度是多少呢?  
首先它有两个 for 循环,每个循环都会走 n 遍,所以这段代码的时间复杂度为 O( n 2 n^2 n2) .

如果将以上代码合并在一起,它们的复杂度是多少?是 O(1) + O(n) + O( n 2 n^2 n2) 嘛?  
不,只是 O( n 2 n^2 n2) .因为当 n 足够大时, O(1) 和 O(n) 对于程序的影响几乎都可以忽略不计,此时我们只需要关注最大量级即可.

接下来说说,空间复杂度计算:  
什么是空间复杂度呢?是指执行当前算法需要占用的内存空间大小.也就是看使用了几个辅助变量.  
照样上几段代码来看看.

void fun(int n){ 
      int var = 3;
      ...
    }

对于这段代码来说,它的空间复杂度是多少?  
应该比较容易看出来,只使用了一个辅助变量,所以它的空间复杂度为 O(1).

void fun(int n){ 
      int[] array = new int[n];
      ...
    }

这段代码,申请了一个大小为 n 的数组,所以它是申请了 n 个辅助变量,所以它的空间复杂度为 O(n).这段代码是申请了一维的,如果是这样呢:

void fun(int n){ 
      int[][] matrix = new int[n][n];
      ...
    }

你一定猜到了,它的空间复杂度是 O( n 2 n^2 n2)