不了解时间空间复杂度，别说你是程序员

来源：公众号程序员小朱 ， 
作者 朱瑶

1、前言

前几天面试了几位java开发人员先不说算法如何，竟然都不知道时间复杂度和空间复杂度。下面我讲一讲什么是时间复杂度和空间复杂度吧。

2、时间复杂度

定义

一般情况下，算法中 基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等 于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

如何推导出时间复杂度有以下原则：

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

举例说明：

T(n) = O(1),执行次数是常量

void dome1(int n) { System.out.println("你好");}

T(n) = O(logn),执行次数是对数

void dome3(int n) { for (int i = n; i > 1; i /= 2) { System.out.println("你好"); }}

T(n) = O(n),执行次数是线性

void dome2(int n) { for (int i = 0; i < n; i++) { System.out.println("你好"); }}

T(n) = O(n2)，执行次数是多项式

void dome4(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println("你好"); } }}

总结

随着n的增长，哪个需要的时间最长呢？

O(1) < O(logn) < O(n) < O(n2),当然时间复杂度不止这些，上面只是取了常用的来说明。

下面给出一张表自己体会下：

3、空间复杂度

定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

S(n) = O(1)，存储空间固定

void dome1(int n) { int i = 3;}

S(n) = O(n)，线性空间

void dome2(int n) { int[] i = new int[n];}

S(n) = O(n2)，二维空间

void dome3(int n) { int[][] i = new int[n][n];}

总结

随着n的增长，哪个需要的空间最大呢？

O(1) < O(n) < O(n2),当然空间复杂度不止这些，上面只是取了常用的来说明。

4、时间与空间的关系

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间;反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。所以在很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍

牺牲时间来换取换空间

void dome(){ int[] array = {2, 3, 6, 1, 5, 2, 4, 9, 7, 8}; for (int i = 0; i < array.length; i++) { for (int j = 0; j < i; j++) { if (array[i] == array[j]) { System.out.println(i + "," + j); return; } } }}

牺牲空间来换取换时间

void dome2(){ int[] array = {2, 3, 6, 1, 5, 2, 4, 9, 7, 8}; Mapmap = new HashMap<>(16); for (int i = 0; i < array.length; i++) { if (map.get(array[i]) == null) { map.put(array[i],1); }else { map.put(array[i], map.get(array[i]) + 1); } } for (Integer key : map.keySet()) { if (map.get(key) == 2) { System.out.println(key); return; } }}

下面给出一个常用排序算法的时间和空间复杂度作参考：