前面的章节知识(点击跳转即可哦)

1 数据类型

2 类型转换

3 运算符

4 逻辑控制

5 输入输出

6 方法的使用

方法递归

7 数组的定义与使用

8 类和对象 -上

8 类和对象-下

目录

• 9 时间复杂度和空间复杂度
• • 9.1 时间复杂度
  • 9.2 空间复杂度

9 时间复杂度和空间复杂度

9.1 时间复杂度

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，就是算法的时间复杂度。

实际中我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数，所以我们使用大O的渐进表示法。

大O符号(Big O notarion): 是用于描述函数渐进行为的数学符号。

大O阶函数的推到原则：

1. 用常数1来代表所有的加法常数。 10 、 2 -> 1
2. 最后的大O函数只保留最高阶项
3. 若最高阶项还有系数，去掉这个系数，保留1 即可， 3N^2 -> N^2

// 请计算一下fun1基本操作执行了多少次？void fun1(int N){   int ret = 0;   // 1   for (int i = 0; i < N ; i++) {for (int j = 0; j < N ; j++) {    ret++;     // N*N}   }   for (int k = 0; k < 2 * N ; k++) { 2Nret++;   }   int M = 10;  while ((M--) > 0) { //10ret++;   }

执行次数就是 N^2 + 2N + 10 + 1, 随着N的变大，只有最高阶项是影响这个算法的核心。所以它的时间复杂度是 O(N^2)。

算法的时间复杂度还分为三种情况：

1. 最坏时间复杂度
2. 最好时间复杂度
3. 平均情况的时间复杂度

最坏时间复杂度

就是这个算法最大的运行时间。假如我们在一个数组个数为 N的数组内查找一个数字a,我们遍历整个数组，当这个数在数组的最后一个，这时就是最坏时间复杂度。O(N)

最好时间复杂度

当这个数在数组的第一个，刚开始遍历就找到了。O(1)

平均情况的时间复杂度

就是所有情况 / 情况的个数

一般我们以最坏时间复杂度当做算法的时间复杂度

还有这种情况

// 计算fun3的时间复杂度？void fun3(int N, int M) {int count = 0;  // 1for (int k = 0; k < M; k++) {  // M   count++;}for (int k = 0; k < N ; k++) {  //N   count++;}System.out.println(count);}

此时M和N都是变量，无法确定谁大谁小，这种情况的时间复杂度就是O(M+N)。

// 计算二分查找的时间复杂度？int binarySearch(int[] array, int value) {   int begin = 0;   int end = array.length - 1;   while (begin <= end) {  // nint mid = begin + ((end-begin) / 2);   //  n/2if (array[mid] < value)    begin = mid + 1;else if (array[mid] > value)    end = mid - 1;else    return mid;   }   return -1;}

不要看见循环就是 O(n),还要看这个循环下次开始条件是什么

在二分查找中，下一次循环的开始或者终止就变成了区间的一半， 最后执行的次数就是 n / 2 / 2/ 2… = 1, 最后求执行了多少次除法操作。

log₂N -> 都可以通过换底公式换为 lg

O(logN) 就是对数时间复杂度，与底数无关。

任何算法，若是不断 去除 任意数字，最后等于0 或者 1，这个算法的执行次数就是O(logN)。

快速排序就是对数级别的算法，O(nlogn)

一个递归函数的时间复杂度，要把这个递归函数展开，看一下递归的次数与变量N的关系。

// 计算阶乘递归的时间复杂度？long factorial(int N) { return N < 2 ? N : factorial(N-1) * N;}

拆开就是 n * n-1 * n-2 * n-3 * … * 1 => 相当于乘了N次 O(n)

// 计算斐波那契递归fibonacci的时间复杂度？int fibonacci(int N) { return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);}

实际上就是一颗二叉树的结点个数 2^n - 1 => O(2^n),这种算法大概率没办法用。

主要掌握O(1) , O(N) ,O(N^2) , O(logN), O(nlogn)。

9.2 空间复杂度

空间复杂度指的是 算法在执行过程中 额外开辟的内存空间！！

就看算法中有没有额外开辟“数组”空间

// 计算冒泡排序的空间复杂度？void bubbleSort(int[] array) {//这是外部传入的数组，不算我们算法自己产生数组，不算到空间复杂度的一部分for (int end = array.length; end > 0; end--) {     boolean sorted = true;     for (int i = 1; i < end; i++) {  if (array[i - 1] > array[i]) {      Swap(array, i - 1, i);      sorted = false;  }     }     if (sorted == true) {  break;     } }}

只有临时变量，没有开辟新的数组，空间复杂度就是 O(1),

要是定义了一堆变量，且这些变量的个数与N有关，int[] data = new int[n], => O(N)。

// 计算fibonacci的空间复杂度？int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {  fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; }return fibArray;}

开辟了一个长度为n+1的long数组，这个算法的空间复杂度就是O(n)

递归函数的空间复杂度

// 计算阶乘递归的空间复杂度？long factorial(int N) { return N < 2 ? N : factorial(N-1)*N;}

每次函数的调用过程，就对应一个函数的”栈帧“在栈中的入栈过程，递归函数调用几次，就需要开辟多少个栈帧空间

这个代码的空间复杂度就是O(N)

要是对大家有所帮助的话，请帮我点个赞吧。