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

前言

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

一般情况下，算法中 基本操作重复执行的次数是问题规模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(n²)，执行次数是多项式

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(n²),当然时间复杂度不止这些，上面只是取了常用的来说明。

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

空间复杂度

定义

空间复杂度(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(n²)，二维空间

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

总结

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

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

时间与空间的关系

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

牺牲时间来换取换空间

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;
        }
    }
}

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

</section>