【时间复杂度和空间复杂度】简单理解与学习

前言

学习算法之前，我们需要先搞懂时间复杂度和空间复杂度。顾名思义，时间复杂度和空间复杂度是一个判断算法好坏的一个标准。时间复杂度就相当于运行代码花费的时间，空间复杂度则代表代码所占用的内存空间。在实际的工作环境中，自然是运行快，占用空间少的代码更具优势。就像一道数学题它本身有多种解法，我们都偏向去使用更简单、更巧妙的方法。

时间复杂度

首先呢，在一个算法中，语句执行的次数称之为语句频度或时间频度，记为T(n)，并且一个算法花费的时间是和时间频度成正比的。n是问题的规模，n不断变化时，T(n)也会不断变化。为了更清晰地明白这个变化所呈现出来的规律，我们就引入了时间复杂度。注意：T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

算法中重复执行地次数是问题规模n的某个函数，我们记为T(n)，并使用某个辅助函数f(n)，当n趋于无穷大时，T(n)/f(n)趋于某个不等于零的常数，则称f(n)为T(n)的同数量级函数，记作T(n)=O(f(n))。

我们不仅要知道什么是时间复杂度，并要会如何计算出某个算法的时间复杂度。

• 常数阶O(1)

在不同算法中，只要算法中语句执行次数为一个常数，则它的时间复杂度就为O(1)

1 public static void way01(int n){
2     int a=0;
3     int b=1;
4     int c=a+b;
5     System.out.println(c);
6 }

注意：只要代码不存在循环、递归等循环类调用，那么无论算法中执行多少条语句，只要为常数，那它的时间复杂度就为常数阶O(1).

• 线性阶O(n)

1 public static void way02(int n){
2     int a=0;
3     for(int i=0;i<n;i++){
4         a+=i;
5     }
6     System.out.println(a);
7 }

以上，我们假设一条语句执行时间为t，则T(n)=t+t*n,而在算法中有一个原则，就是常量可以忽略不计，那么t+tn---->tn---->n，则可记为O(n)。并且不同算法，它们的时间复杂度也可能是相同的。例如T(n)=n+2与T(n)=3n+4,由于常量可以忽略，则变成O(n+2)=O(n),O(3n+4)=O(3n)=O(n),则它们的时间复杂度均为O(n)。

• 平方阶O(n^2)

与线性阶类似，比如T(n)=n²+n+2与T(n)=3n²+2n+4,分别表示O(n²+n)、O(3n²+2n)------>O(n(n+2))、O(3n(n+2/3))------>O(n²)、O(3n²)----->均为O(n²)。

• 对数阶O(logn)

对数阶相较而言有些麻烦，不过也好理解，下面通过例子解释：

1 public static void way03(int n){
2     int a=1;
3     while(a<=n){
4         a*=2;
5     }
6 }

假设while循环中循环x次，则2^x=n,x=log₂n,则T(n)=1+log₂n。同理，当a*=3、a*=4……时，那么T(n)=log₃n,T(n)=log₄n……，且T(n)=log₃n=log₃2*log₂n,则他们的时间算法复杂度为O(log₂n),实际表达中，我们直接记为O(logn)。

• 线性对数阶O(nlogn)

与对数阶类似

1 public static void way04(int n){
2     int a=1;
3     for(int i=0;i<n;i++){
4         while(a<=n){
5             a*=2;
6         }
7     }
8 }

显然，O(n)=1+nlogn=nlogn

以上就是时间复杂度的一些简单理解和计算，这里面当然还会有其他更深入的知识，这里就不过多赘述了。

空间复杂度

空间复杂度是指算法在计算机执行时所需存储空间的度量，记为S(n)=O(f(n))

算法所占用的空间主要分为三大类：一、算法本身占用的空间，二、算法的输入输出数据所占用的空间，三、运行过程中所临时占用的空间

这里讨论的是除正常占用内存开销外的辅助存储单元。

空间复杂度的分析与时间复杂度类似，当一个算法的空间复杂度为一个常数（他不随n的改变而改变）时，记为O（1）。若算法里面出现数组、列表、栈等它们会随着n的改变而改变占用内存空间的大小，比如一维数组nums,它的长度为n，则其空间复杂度就记为O(n)，其他类型同理。

补充：

当一个算法中出现T(n)=O(n²)+O(n)+O(1),则选择复杂度最高的那一个，即T(n)=O(n²),如果出现了两个复杂度相同的，比如T(n)=O(n)+O(m)+O(1)，则记为它们之和O(m+n)。