实例4：
计算bubbleSort的时间复杂度？
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;
}
}
}
🛸🛸解答：
这里就要用到我们的最好情况和最坏情况了，我们可以发现冒泡排序最好的情况下是执行了N次，即数组是有序的，只要遍历到每一个元素即可；那么最坏的情况就是数组是倒序的，那么第一个元素就要和每个其余的元素相比较，比较次数是n-1 第二个元素比较次数就是N-2 ……依次到最后比较一次，那么总共的比较次数就是1+2+……+（n-1）次，根据等差数列求和得最后的次数为
(N*(N-1))/2；在根据大O阶推导法，所以fun4的时间复杂度就是O(n^2);
实例5：
计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
🚛🚛解答：
我们可以发现基本操作递归了N次，根据递归的时间复杂度= 递归的次数*每次递归执行的次数
——>时间复杂度为O(N)。
实例6：
计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
🚐🚐解答：
这一题是求斐波那契数列第n项的值，我们可以发现当我们要求第n项的值时，我们需要知道第n-1项和n-2项的值，而要求的第n-1项的值，我们需要求出n-2项的值，如此下去，我们可以发现，基本操作呈现二叉树的形式分布，最后可以推导出fibonacci（）的时间复杂度为O(2^N);
二、空间复杂度
🚚🚚上面已经提到，空间复杂度是对一个算法在运行过程中临时占用多少内存空间大小的量度，那么我们的空间复杂度也是用大O渐进表示法！
下面我们看几个实例：
实例1：计算bubbleSort的空间复杂度？
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;
}
🚔🚔解答：
可以发现我们的函数参数传进来一个数组array（实际上传的是array首元素的地址），我们在函数的执行过程中并没有开辟新的空间，所以空间复杂度为O(1)。
实例2：计算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项的值时动态开辟了N个空间，所以空间复杂度为 O(N)。
实例3：计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
🛵🛵解答：根据我们的时间复杂度已经计算过的，我们可以了解到递归调用了N次，所以开辟了N个栈帧，每个栈帧使用了常数个空间，所以空间复杂度为O(N)，即可以理解为当我们的n-1 在执行完毕的时候会释放栈空间，这个时候在执行右边的n-2，所以最终开辟的空间大小以最深的来理解，如图蓝色箭头所示，即为N.
