时间复杂度高级

简介: 时间复杂度高级

实例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);

774f999a0f404c4bb57e24b9a8d859ed.png二、空间复杂度

🚚🚚上面已经提到,空间复杂度是对一个算法在运行过程中临时占用多少内存空间大小的量度,那么我们的空间复杂度也是用大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.

2cc17dc4d3a54915ae5332321188ae0e.png


相关文章
|
7月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——算法的时间复杂度和空间复杂度
算法的时间复杂度和空间复杂度是评估算法性能的两个重要指标。时间复杂度主要关注算法执行过程中所需的时间随输入规模的变化情况,而空间复杂度则关注算法执行过程中所需的最大存储空间或内存空间。
339 0
|
5月前
|
搜索推荐 算法 C++
|
6月前
|
算法
数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题
数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题
44 2
|
7月前
|
算法
时间复杂度在编程中的应用与实例分析
本文主要分享了时间复杂度在编程中的应用与实例分析
114 3
|
算法
【基础知识整理】时间复杂度 & 空间复杂度
时间复杂度与空间复杂度的作用是在衡量一个算法的优劣性,以及在二者之间进行权衡,寻找二者的平衡点。
|
7月前
|
算法 索引
二分查找算法案例
二分查找算法案例
70 0
|
机器学习/深度学习 算法
深入浅出理解:算法的时间复杂度和空间复杂度
深入浅出理解:算法的时间复杂度和空间复杂度
65 0
|
机器学习/深度学习 存储 算法
从头开始:数据结构和算法入门(时间复杂度、空间复杂度)
从头开始:数据结构和算法入门(时间复杂度、空间复杂度)
56 0
|
算法 搜索推荐
开发工程师-常用算法基本思想 -分类-时间复杂度与空间复杂度概述
开发工程师-常用算法基本思想 -分类-时间复杂度与空间复杂度概述
数据结构之排序【归并排序和快排的顶级优化和快排的三种原理的实现及分析】 内含动态演示图
引言: 1.归并排序(MergeSort) 2.快速排序的优化(顶级优化) 3.快速排序的三种思路的代码实现及分析 4.归并排序和快排第3原理的测试