算法复杂度介绍

评判算法的优劣，通常是有两个指标：时间和空间两个维度。

时间维度是指执行一段代码中的算法所消耗的时间。

空间维度是指执行一段代码需要占用的内存空间。

一、时间复杂度

判断一个算法的好坏，不能单纯的在一台计算机上去执行，看它的执行时间来判断，因为执行时间的长短，也会受到环境的影响，比如计算机的配置，数据的规模等。

通常会通过大 O 符号表示法：T(n)=O(f(n)),其中 f(n) 表示执行代码的次数

如下的代码:

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

这里假设每行代码执行时间的大小相同，为 t, 那这里 1+2nt，则 T(n) =O(1+2nt) , 可以看到这里的 T(n) 是和 n 有关的一个函数，如果 n 趋向于无穷大，那常量 1 没有太大意义，而 2n 也是一个无穷大的数值，可以直接使用 n 表示，所以 T(n) = O(n) 来表示了。

在判断一个算法好坏时，通常都以算法的 O 的表达式来评判，常见的 O 的时间的复杂度有：

1、常量阶(O(1))

正常的一行代码就是一个常量阶，如 i++,这种情况是效率最好的

2、线性阶(O(n))

如上面举例的 for 循环，和循环的次数有关系

3、对数阶(O(logn))

如二分查找法，假设 N 个数据，每次 N/2^x=1, 1 是最后找到的数据，所以 x=logN

4、线性对数阶(O(NlogN))

这种方式，可以理解为有 M 个数组，从每个数组中找出对应的值，如

for(int i=0;i<M;i++){	// 二分查找法    binarySearch();}

5、平方阶(O(n²)) 或是 N 的 K 次方（K>=2）

最常见的是两个或是 K 个 for 循环嵌套

时间复杂度的效率关系(按执行时间)

O(1) < O(logN) < O(N) < O(NlogN) < O(N^K)

对于时间复杂度而言，这个 N 的值比较重要，如果是很小的情况下，其实不太能比对出一个算法的好坏，通常是要 N 比较大的前提下来看一个算法的效率。

二、空间复杂度

空间复杂度是对于在算法执行过程中临时占用的空间的一个评估度量，一般使用 S(n) = O(f(n)) 来表示，比如常见的是 O(1)、O(n)

1、 O(1)

和时间复杂度类似，不会随着 N 的变化而变化，如 int i = 0;b=4;

2、O(n)

比如常见的是创建数组，如

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

三、时间与空间的转换

对于算法来说，时间复杂度与空间复杂度都是会互相影响的。正常情况下时间复杂度低，效率高的算法，对于空间的要求都是比较高的，比如跳表算法就是以空间换时间来提高链表遍历的效率。