Java 时间复杂度和空间复杂度

文章目录

1.算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间

2.时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间

大O渐近表示法

计算时间复杂度和空间复杂度时，为了估算一个算法的耗时情况，不需要计算出精确的执行次数，只需要计算到一个大概的计算次数次数即可，我们使用大O渐近表示法

O（）->是一个函数渐近的数学符号

1.常数1表示所有的加法常数 1000或者10000只保留1

2.最后的大O函数只保留最高项，N^ 2+N+100只保留N^2

3.若最高阶还有系数，去除系数，3N^ 2或者2N^ 2只保留N^2

此时一共执行次数为：N^2+2N+10

时间复杂度：O（N^2）

此时执行次数:N+M,由于无法判断N和M的大小，所以时间复杂度：O（N+M）

此时执行次数100次，时间复杂度：O（1）

千万看到有N就是O（N）

这个算法在下一次循环时起始位置或者末位置就变成了区间的一半，每次变为原先的一半，执行次数：O(logN)

任意算法，如果不断/任意数字，最终等于1或者0，这个算法的时间复杂度就是O（logN）

一个算法能做到对数级别那么一定是一个优秀的算法

一个递归函数的时间复杂度，要展开这个递归函数，看递归了多少次

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

一共递归了n-1次，这个算法的时间复杂度O（n）

斐波那契函数的递归

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

计算这个递归函数的时间复杂度比较特殊，递归次数是二叉树的结点个数2^n -1

时间复杂度为O（2^n）

重点掌握O（1）O（n）O（n^2）O（logn）O（nlogn）

最坏情况的时间复杂度：这个算法的最大运行时间

最好情况的时间复杂度：这个算法的最小运行时间

平均情况的时间复杂度：这个算法的平均运行时间

当前数组的个数为n，从头开始遍历，如果所需的元素在末尾就是最坏情况的时间复杂度O（n），如果所需的元素在第一个就是最好情况的时间复杂度O（1），如果所需的元素在中间就是O（n/2）

3.空间复杂度

所谓空间复杂度指的是算法中”额外”开辟的内存空间

计算空间复杂度也使用大O渐近法

一般来说空间复杂度就看算法中有没有开辟”数组”空间

像这种没有额外开辟内存的就是O（1）

long[] fun8(int n) {long[] arr = new long[n+1];//在堆开辟了一个长度为n+1的数组就是O（n）arr[0] =0;arr[1] = 1;for (int i = 2; i < n; i++) {arr[i] = arr[i-1]+arr[2];}return arr;}

开辟了一个长度为n+1的数组就是O（n）

当只定义了几个临时变量，O（1）

定义了一些变量，而且这些变量的个数与N有关

int[] data = new int[n] => O(n)

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

这个递归函数递归了n-1次，空间复杂度：O（n）

void fun9(int n) {if(n==1) {return;}int[] arr = new int[n];fun9(n-1);}

这个递归函数会调用n次，每次调用开辟一个长度为n的数组

空间复杂度：O（n^2）