[Java高级]（三）时间复杂度计算

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[Java高级]（三）时间复杂度计算，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2637字，纯文字阅读大概需要4分钟。

内容图文

正值疫情，家中闭关，早起看新闻确诊人数已过万，不禁唏嘘，在此真切希望长风破浪会有时，直挂云帆济沧海。感激奋斗在一线的医护人员。

时间复杂度

• 1、概念
• 2、各时间复杂度介绍
• 2.1、O(1)
• 2.2、O(logn)、O(nlogn)对数阶时间复杂度
• 2.3、O(m+n)、O(m*n)
• 2.3.1加法法则
• 2.3.2 乘法法则
• 2.3.3 循环不仅与n有关，还与执行循环所满足的判断条件有关。

1、概念

时间复杂度是指算法执行语句执行的次数。
常见的时间复杂度有以下几种：

2、各时间复杂度介绍

2.1、O(1)

O(1)是常量级时间复杂度的一种表示方法，并非只执行一行代码。
代码执行时间不是随着n的增大而增大，这样的代码的时间复杂度都是O(1)。
注意：通常只要算法中不存在循环、递归，即使代码有很多行，时间复杂度仍是O(1)。

2.2、O(logn)、O(nlogn)对数阶时间复杂度

int i = 1;
while(i<=n){
  i=i*2;
}

代码line3是执行次数最多的，只要算出第3行执行的次数，它代表的就是整个代码的时间复杂度。i从1开始取值，每一次循环乘以2。可以看到 i=i*2是一个等比数列，即：2º 2¹ 2² … 2^k 。
只要算出k是多少，就是执行的次数了 2^k=n -->k=log2n，所以时间复杂度应该为O(log2n)。

int i = 1;
while(i<=n){
  i=i*5;
}

很容易就能看出来，应该是O(log5n)。但是上面的O(log2n)和O(log5n)可以通过换底公式换成以2为底的对数，且可以忽略系数，所以都记做 O(logn)。

关于O(nlogn)，就是把上面的代码在循环执行n遍了。其中归并排序、快速排序的时间复杂度就是O(nlogn)。

2.3、O(m+n)、O(m*n)

2.3.1加法法则

加法法则（量级最大法则）：总复杂度等于量级最大的那段代码的复杂度。

  public static Integer getSum(Integer n){
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < 1000; i++){
      sum1 += i;
    }
 
    for (int i = 0; i < n; i++){
      for (int j = 0; j < n; j++){
        sum2 += i*j;
      }
    }
 
    return sum1 + sum2;
  }

sum1和sum2分别是 O(n)和O(n²)，对于这两个，我们取量级最大的O(n²)，所以总的时间复杂度就等于量级最大的那段代码的时间复杂度。

2.3.2 乘法法则

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 。

  public static Integer getSum(Integer n){
    int sum = 0;
    for (int i = 0; i < n; i++){
      sum += func(i);
    }
 
    return sum;
  }
 
  public  static Integer func(Integer x){
    int sum = 0;
    for (int i = 0; i < x; i++){
      sum += i^2;
    }
    return sum;
  }

func()函数的时间复杂度是 T1(n)=O(n)，如果先把func()函数看成简单的操作，则getSum()函数的时间复杂度是T2(n)=O(n)，所以整个getSum()函数的时间复杂度是T(n)=T2(n)T1(n)=O(nn)=O(n^2) 。

2.3.3 循环不仅与n有关，还与执行循环所满足的判断条件有关。

  public  static Integer func(Integer x, Integer[] arr){
    int sum = 0;
    int i=0;
    while (i < x && arr[i]!=1)
    {
      i++;
      sum += arr[i];
    }
    return sum;
  }

在此循环，如果arr[i]不等于1的话，时间复杂度是O（n）。如果arr[i]等于1的话，则循环执行一次判断跳出，时间复杂度是O(1)。

常见算法的时间复杂度以及空间复杂度如下：

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的[Java高级]（三）时间复杂度计算全部内容，希望文章能够帮你解决[Java高级]（三）时间复杂度计算所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端