【Java】时间复杂度与空间复杂度

前言

我们评估一个程序的好坏，通常是以程序执行的速度以及程序所占用的内存为依据。自本篇开始，我们进入了数据结构的学习，本篇介绍时间复杂度及空间复杂度的计算

---

1. 时间复杂度

1.1 计算方法

时间复杂度，指的是基本语句的执行次数。
例1

  public void fun(int n){
         int t = 1;
         for(int i = 0; i < n; i++){
             t++;
         }
    }
1
2
3
4
5
6

如上图，基本语句执行了n+1次

例2

 void fun2(int n){ 
         int y = 1;
         for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                y++;
            }
        }
    }
1
2
3
4
5
6
7
8

如上图，基本语句执行了n²+1次。

例3

public void fun(){
         int t = 1;
         for(int i = 0; i < 10; i++){
             t++;
         }
    }
1
2
3
4
5
6

如上图，基本语句执行次数为11

1.2 时间复杂度表示原则

1. 用O（）来作为时间复杂度的公式
2. 若基本执行次数为固定常数，则时间复杂度统一为1，用O(1)表示，例3中时间复杂度就是O(1)
3. 若基本操作执行次数是一个复合表达式，则取次数最高项，去掉系数，就是时间复杂度。如例2中，取n²,时间复杂度为O(n²),为什么这样取舍呢，因为当n趋于无穷大是，1相对n²来说过小，可忽略不计。如果是3n³+n²呢，时间复杂度是O(n³),依然是取最高项，去掉系数。
4. 在实际应用中，例如遍历n*n二维数组找某个元素，运气好的时候，第一个元素就是，执行次数是1，运气不好，元素全部遍历完事之后，才找到元素，执行次数为n².时间复杂度通常指的是最坏情况下的复杂度。

1.3 练习题

例1 冒泡排序

 static void mySort(int[] array){
         for(int i = 0; i < array.length-1; i++){
             boolean flg = true;
             for(int j = 0; j < array.length - i -1; j++){
                 if(array[j] > array[j+1]){
                     int temp = array[j];
                     array[j] = array[j+1];
                     array[j+1] = temp;
                     flg = false;
                 }
             }
             if(flg == true){
                 break;
             }
         }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最坏的情况是，循环执行完毕时的操作次数。为n-1+n-2+n-3+·····0，是一个等差数列，最高项为n².时间复杂度为O(n²)

例2 二分排序

  static int searchValue(int[] array, int value){
        int left = 0;
        int right = array.length-1;
        while(left <= right){
            int mid = (left + right)/2;
            if(array[mid] > value){
                right = mid - 1;
            }else if(array[mid] < value){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最坏的情况是，到最后，只剩下一个数才是value的时候，此时，n / 2^x = 1,x = logⁿ.时间复杂度为
O（logⁿ）

例3 阶乘

 int factorial(int n){
        return n < 2 ? n : n * factorial(n-1); 
   }
1
2
3

函数总共执行了n次，时间复杂度为O(n)

例4 求斐波那契数列

int fabonacci(int n){
        return n < 2 ? n : fabonacci(n-1)+fabonacci(n-2);
   }
1
2
3

每次执行2^n-1次函数，总共加起来是一个等比数列，最高项是2ⁿ,时间复杂度为O(2ⁿ).

2. 空间复杂度

空间复杂度，指的是程序所占内训的大小，以变量个数为依据。这里的变量不包括临时变量。
例1

static void mySort(int[] array){
         for(int i = 0; i < array.length-1; i++){
             boolean flg = true;
             for(int j = 0; j < array.length - i -1; j++){
                 if(array[j] > array[j+1]){
                     int temp = array[j];
                     array[j] = array[j+1];
                     array[j+1] = temp;
                     flg = false;
                 }
             }
             if(flg == true){
                 break;
             }
         }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里的形参是临时变量，变量flg每次都会循环刷新，所以，这个函数的空间复杂度为O（1）。

例2

 void fun2(int m,int n){
         int y = 1;
         int[] array = new int[10];
         for(int i = 0; i < m; i++){
             array[i] = i;
            for(int j = 0; j < n; j++){
                y++;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

里面有m+1个变量，所以空间复杂度为O（m）.
例3

 int fabonacci(int n){
        return n < 2 ? n : fabonacci(n-1)+fabonacci(n-2);
   }
1
2
3

递归每次调用函数，就会开辟一个空间，每return一次，就会有一个空间，总共开辟n个，空间复杂度为O（n）.

---