时间复杂度与空间复杂度，看这一篇就够了

作者：Runsen

目录

• 1. 时间复杂度
• 1.1 定义
• 1.2 推导时间复杂度的原则
• 1.3 各时间复杂度曲线
• 1.4 常见时间复杂度
• 2. 空间复杂度
• 2.1 定义
• 2.2 常用空间复杂度

1. 时间复杂度

1.1 定义

若存在函数 ，使得当 趋向无穷大时， 的极限值为不等于 0 的常数，则称 是 的同数量级函数，记作 ，称 为算法的渐进时间复杂度，简称 时间复杂度，用大 O 来表示，称为大 O 表示法；

1.2 推导时间复杂度的原则

1. 若运行时间是常数量级，则用常数 1 表示；
2. 只保留时间函数中最高阶项，如 ，保留最高阶项后，成为 ；
3. 若最高阶项存在，则省去最高阶项前的系数；

1.3 各时间复杂度曲线

1.4 常见时间复杂度

即无论执行执行多少行，都不会影响到其他区域，此时代码的复杂度就是

void sayHello(String name){
    System.out.prinln("Hello, " + String);
}

如下列二分查找代码中，通过 while 循环，能够成倍的缩减搜索范围，假设需要 x 次才能跳出循环，则有 num * 2 * 2 * ... = n ，其中num 是常数，有 n 个 2 相乘，则有 ，从而推出 ，因此时间复杂度用大 O 表示法表示为

int binarySearch(int[] arr, int target){
    int left = 0;
    int right = arr.length - 1;
    while(left <= right){
        int middle = left + (left - right) / 2;
        if(arr[middle] == target){
            return middle;
        }else if(arr[middle] > target){
            right = middle - 1;
        }else {
            left = middle + 1;
        }
    }

    return -1;
}

如下面这段代码中，for 循环中的代码被执行了 arr.length 次，因此所需要的时间和数组长度成正比的，因此可以用 来表示它的时间复杂度

int sum(int[] arr){
    int total = 0;

    for(int i = 0; i < arr.length; i++){
        total += arr[i];
    }

    return total;
}

如果我们将一个复杂度为 的代码重复执行 次，那么此时代码的复杂度不就变成 了吗

void hello (int n){
  for( int i = 1 ; i < n ; i++){
    int m = 1;
    while( m < n ){
        m *= 2;
    }
   }
}

假设我们将时间复杂度为 的代码重复执行 次，那么此时的时间复杂度就是 ，即可表示为 ，表现出来就是双重循环的形式

void selectionSort(int[] arr, int n){
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[min]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

和 ，类似，将时间复杂度为 的代码嵌套循环一次，此时复杂度就变成了 ，表现出来就是三重循环嵌套的形式

void demo(int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                System.out.print("Hello, World");
            }
            System.out.print("------");
        }
        System.out.print("******");
    }
}

虽然理论上存在时间复杂度为 的算法，但实践中基本遇不到，所以这里就不展开了

2. 空间复杂度

2.1 定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度（即除开原始序列大小的内存，在算法过程中用到的额外的存储空间），反映的对内存占用的趋势，而不是具体内存，用 来代替；

2.2 常用空间复杂度

算法执行所需临时空间不随某一变量 n 的大小而变化，则该算法空间复杂度为一个常量，表示为 ；

int num1 = 1;
int num2 = 2;
int total = num1 + num2;

数组占用内存大小为 n，而且后续未分配新的空间，因此该算法空间复杂度为 ；

int[] arr = new int[n];

后面附上多种排序的时间复杂度