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

村雨遥

发布于 2020-07-02 23:54:35

1.4K00

代码可运行

文章被收录于专栏：JavaParkJavaPark

运行总次数：0

代码可运行

1. 时间复杂度

1.1 定义

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

1.2 推导时间复杂度的原则

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

1.3 各时间复杂度曲线

1.4 常见时间复杂度

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

void sayHello(String name){
    System.out.prinln("Hello, " + String);
    System.out.prinln("欢迎关注我的公众号：【村雨遥】");
}

如下列二分查找代码中，通过 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];

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-06-27，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自村雨遥微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度