Java时间复杂度与空间复杂度,记一次字节跳动Java研发岗的面试经历【附源码】_程序员lwx

2.2 大O的渐进表示法

 // 请计算一下func1基本操作执行了多少次?  void func1(int N){     int count = 0;     for (int i = 0; i < N ; i++) {         for (int j = 0; j < N ; j++) {             count++;         }     }     for (int k = 0; k < 2 * N ; k++) {         count++;     }     int M = 10;    while ((M--) > 0) {         count++;     }    System.out.println(count);  }  

Func1 执行的基本操作次数 :

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

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

大O符号(Big O notation):

是用于描述函数渐进行为的数学符号。

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中,只保留最高阶项。

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后,Func1的时间复杂度为

N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界)

例如:

在一个长度为N数组中搜索一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

2.3常见时间复杂度计算举例

实例1:

 // 计算func2的时间复杂度?  void func2(int N) {  int count = 0;  for (int k = 0; k < 2 * N ; k++) {     count++;  }  int M = 10;  while ((M--) > 0) {     count++;  }  System.out.println(count);  }  

实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

实例2:

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

实例2基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

实例3:

 // 计算func4的时间复杂度?  void func4(int N) {  int count = 0;  for (int k = 0; k < 100; k++) {     count++;  }  System.out.println(count);  } 

实例3基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)

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

实例4基本操作执行最好N次,最坏执行了(N*(N-1))/2次,通过推导大O阶方法+时间复杂度一般看最坏, 时间复杂度为 O(N^2)

实例5:

  // 计算binarySearch的时间复杂度?  int binarySearch(int[] array, int value) {     int begin = 0;     int end = array.length - 1;     while (begin <= end) {         int mid = begin + ((end-begin) / 2);         if (array[mid] < value)             begin = mid + 1;         else if (array[mid] > value)             end = mid - 1;  # 总结  在这里,由于面试中MySQL问的比较多,因此也就在此以MySQL为例为大家总结分享。但是你要学习的往往不止这一点,还有一些主流框架的使用,Spring源码的学习,Mybatis源码的学习等等都是需要掌握的,我也把这些知识点都整理起来了  **[CodeChina开源项目:【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](https://ali1024.coding.net/public/P7/Java/git)**  ![面试真题](https://s2.51cto.com/images/20210919/1632035058760702.jpg)  ![Spring源码笔记](https://s2.51cto.com/images/20210919/1632035058633610.jpg)

本站由小牛团队全力维护,小牛十年了,大家已经步入中年 。本站源码全部经过团队成员测试并调试,价格可能比其它网站略贵几元钱,不解释!
小牛资源 » Java时间复杂度与空间复杂度,记一次字节跳动Java研发岗的面试经历【附源码】_程序员lwx

发表评论

全站资源亲测可用,价格略高几元,不解释

立即查看 了解详情