精华内容
下载资源
问答
  • java时间复杂度计算

    千次阅读 2019-09-03 22:19:29
    时间复杂度是指算法执行语句执行的次数。 常见的时间复杂度有以下几种: 描述 时间复杂度 常数阶 O(1) 对数阶 O(logn) 线性阶 O(n) 线性对数阶 O(nlogn) 平方阶 O(n²) 立方阶 O...

    时间复杂度是指算法执行语句执行的次数。

    常见的时间复杂度有以下几种:

    描述时间复杂度
    常数阶O(1)
    对数阶O(logn)
    线性阶O(n)
    线性对数阶O(nlogn)
    平方阶O(n²)
    立方阶O(n³)
    n次方阶O(mⁿ)
    指数阶O(2ⁿ)
    阶乘阶O(n!)

     (1) O(1)

    O(1)是常量级时间复杂度的一种表示方法,并非只执行一行代码。

    代码执行时间不是随着n的增大而增大,这样的代码的时间复杂度都是O(1)。

    注意:通常只要算法中不存在循环、递归,即使代码有很多行,时间复杂度仍是O(1)

    (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 = n。只要算出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)

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

    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.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 。

      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(n*n)=O(n^2) 

    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)。


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

    附:

        链表实现与时间复杂度分析

        数组算法时间复杂度

        红黑树的插入和遍历时间复杂度分析

    展开全文
  • 时间复杂度是指 算法执行语句执行的次数。 常见的时间复杂度有以下几种: 描述 时间复杂度 常数阶 O(1) 对数阶 O(logn) 线性阶 O(n) 线性对数阶 O(nlogn) 平方阶 O(n²) 立方阶 O(n³) n次方阶 ...

    时间复杂度是指 算法执行语句执行的次数。

    常见的时间复杂度有以下几种:

    描述时间复杂度
    常数阶O(1)
    对数阶O(logn)
    线性阶O(n)
    线性对数阶O(nlogn)
    平方阶O(n²)
    立方阶O(n³)
    n次方阶O(mⁿ)
    指数阶O(2ⁿ)
    阶乘阶O(n!)

    (1) O(1)

    O(1)是常量级时间复杂度的一种表示方法,并非只执行一行代码。

    代码执行时间不是随着n的增大而增大,这样的代码的时间复杂度都是O(1)。

    注意:通常只要算法中不存在循环、递归,即使代码有很多行,时间复杂度仍是O(1)

    (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 = n。只要算出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)

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

    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²),所以总的时间复杂度就等于量级最大的那段代码的时间复杂度。

    1. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    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)

    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 sourcemonitor圈复杂度计算

    千次阅读 2015-01-20 21:36:01
    转载文章 sourcemonitor集成至eclipse的方法:   1、安装sourcemonitor工具 2、run New_Configration菜单 -> External Tools Configurations..... 设置参数:/DJava${container_loc}/${resource_...圈复杂度(Cycloma

    转载文章


    sourcemonitor集成至eclipse的方法:

      
    1、安装sourcemonitor工具  

    2、run New_Configration菜单 -> External Tools Configurations..  

         设置参数:/DJava${container_loc}/${resource_name}  


    圈复杂度(Cyclomatic Complexity)是一种代码复杂度的衡量标准。它可以用来衡量一个模块判定结构的复杂程度,数量上表现为独立现行路径条数,
    也可理解为覆盖所有的可能情况最少使用的测试用例数。圈复杂度大说明程序代码的判断逻辑复杂,可能质量低且难于测试和维护。程序的可能错误
    和高的圈复杂度有着很大关系。
    下面这个实例中,单元测试的覆盖率可以达到100%,但是很容易发现这其中已经漏掉了一个NPE的测试用例。case1方法的圈复杂度为2,因此至少需要
    2个用例才能完全覆盖到其所有的可能情况。
    //程序原代码,圈复杂度为 2
    public String case1(int num) {
           String string = null;
           if (num == 1) {
               string = "String";
           }
           return string.substring(0);
        }
     //上面代码的单元测试代码
        public void testCase1(){
           String test1 = case1(1);
        }





    圈复杂度主要与分支语句(if、else、,switch 等)的个数成正相关。可以在图1中看到常用到的几种语句的

    控制流图(表示程序执行流程的有向图)。  当一段代码中含有较多的分支语句,其逻辑复杂程度就会增加。

    在计算圈复杂度时可以通过程序控制流图方便的计算出来。通常使用的计算公式是  V(G) = e – n + 2  e代表

    在控制流图中的边的数量(对应代码中顺序结构的部分),n 代表在控制流图中的节点数量,包括起点和终点 

    (1、所有终点只计算一次,即便有多个return或者throw;2、节点对应代码中的分支语句) 



    知道了如何计算圈复杂度,我们来使用控制流图重新计算一次case1方法的圈复杂度,其控制流图如下图。
    状态1表示 if(num == 1 )的条件判断,  状态2表示string=”String”的赋值操作。可以通过下面的控
    制流图得到 e = 4 ; n = 4;那么全复杂度V(G) = 4 - 4 + 2 = 2,既case1的圈复杂度为2

    public String case2(int index, String string) {  
           String returnString = null;  
           if (index < 0) {  
               throw new IndexOutOfBoundsException("exception <0 ");  
           }  
           if (index == 1) {  
               if (string.length() < 2) {  
                  return string;  
               }  
               returnString = "returnString1";  
           } else if (index == 2) {  
               if (string.length() < 5) {  
                  return string;  
               }  
               returnString = "returnString2";  
           } else {  
               throw new IndexOutOfBoundsException("exception >2 ");  
           }  
           return returnString;  
        }  


    根据公式 V(G) = e – n + 2 = 12 – 8 + 2 = 6 。case2的圈复杂段为6。说明一下为什么n = 8,
    虽然图上的真正节点有12个,但是其中有5个节点为throw、return,这样的节点为end节点,

    只能记做一个在开发中常用的检测圈复杂度的工具,PMD,checkstyle ,sourcemonitor都可以检

    测到高复杂度的代码块。在代码的开发中,配合各种圈复杂度的检测插件,将高复杂度的代码

    进行适当的拆分、优化,可以大大提高代码整体的质量,减少潜在bug存在。  


    另外,提下/DJava${container_loc}/${resource_name},可以参考博文[container_loc]  

    百度文库资料[外部工具作为项目构建进程的一部分]

    eclipse所有的插件都会在showView展示出来,比如eclipses->svn插件,当我们要清除

    svn插件中记录的svn目录时,可以在showView中找出svn,然后remove repository

    展开全文
  • 空间复杂度计算

    2020-05-04 13:32:05
    算法空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度计算的公式记作:S(n)=O(f(n)),其中n为问题规模,f(n)为语句关于n所占储存空间的函数。 当一个算法的空间复杂度是常量时,即不随处理数据n变化而变化时...

    空间复杂度

    记录一下以免忘记
    空间复杂度指运行完一个程序所需的内存空间,有时可以用空间来换取时间。
    算法空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度计算的公式记作:S(n)=O(f(n)),其中n为问题规模,f(n)为语句关于n所占储存空间的函数。
    当一个算法的空间复杂度是常量时,即不随处理数据n变化而变化时可记为O(1),空间复杂度的计算与时间复杂度计算大体相同。

     int i = 0;
     int j = 0 ;
      //...后面即使在有10个变量20个,只要内存不随n而改变就可记作O(1)
    
    for(int i = 0;i<n;i++){
    int j = 0;
    }
    

    这段代码中创建了n个j变量所以空间复杂度为S(n) = O(n)。

    for(int i = 0 ; i <n; i ++){
    	for(int j = i ; j< n ; j++){
    		int k = 0;
    	}
    }
    

    一共要创建(n+1)*n/2个变量保留最高项的出空间复杂度S(n)=O(n²)。

    展开全文
  • 复杂度计算

    千次阅读 2019-11-06 17:15:12
    计算公式1:V(G)=e-n+2p。其中, ...其实,圈复杂度计算还有更直观的方法, 因为圈复杂度所反映的是“判定条件”的数量, 所以圈复杂度实际上就是等于判定节点的数量再加上1,也即控制流图的区域数...
  • Are there any tools available for Java that can automagically determine the cyclomatic complexity of given Java code? I have sought out tools online, and have yet to find one.解决方案I use Sonar (my ...
  • 递归算法的时间复杂度计算 递归时间复杂度的计算本质在于 递归次数*每次递归中的操作数 利用二叉树进行递归调用:O(logn),每次递归调用都是n/2。
  • 时间复杂度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、概念 时间...
  • Java复杂度

    2021-02-03 18:03:50
    Java圈复杂度一、圈复杂度概念1、圈复杂度计算规则2、idea圈复杂度插件 MetricsReload圈复杂度优化1、优化表达式2、提炼函数3、简化代码[合并条件式、使用更简洁的表达]4、减少认知复杂度5、工具类替换逻辑判断 ...
  • 递归程序的时间复杂度计算

    千次阅读 2016-11-12 19:19:03
    递归程序的时间复杂度计算
  • 时间复杂度计算方法

    2020-08-16 15:28:21
    1. 常见的时间复杂度和空间复杂度有哪些? O(1): constant complexity: constant 常数复杂度 O(log n): 对数复杂度 O(n): 线性时间复杂度 O(n^2): 平方 O(N^3): 立方 O(2^n): 指数 O(n!): 阶乘 2. 时间...
  • 第一段代码我们可以看出&#...即此算法空间复杂度为一个常量,所以表示为大 O(1) 什么时候的空间复杂度是O(n)? 当消耗空间和输入参数n保持线性增长,这样的空间复杂度为O(n) 来看一下这段代码中
  • 数据结构之复杂度计算 1.时间复杂度 举个例子来说: 数学家高斯小时候的事,计算1+2+。。。+100的和,有两种方法,为 第一种: for(int i=0;i<=100;i++){ sum=sum+i; } 第二种: int n=100 sum=0; sum=(n+1)*n/2;...
  • 首先,我们需要知道的是 时间复杂度计算的是一个程序大致执行了多少个语句(之前我认为是要计算到底执行了多少秒,是我天真了,怎么可能了),时间复杂度计算允许省去一些影响小的因素(比如说后面会提到的n对n2...
  • 2)次比值交换 … 倒数第2轮,经历2次比值交换 倒数第1轮,经历1次比值交换 故,可得,总耗费步骤为:(n-1)+(n-2)+…2+1=[(1+(n-1))(n-1)]/2=(n(n-1))/2=(n²-n)/2=n²/2-n/2,根据时间复杂度计算原则,去掉常量,低...
  • Java时间复杂度与空间复杂度.pdf
  • Java时空复杂度

    2020-08-03 21:18:33
    Java时空复杂度算法效率时间复杂度空间复杂度 算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的...
  • 学习算法的同学,如果不知道计算一个算法的时间复杂度该如何计算,其实是一件很丢脸的事情。最近选修了高级算法这门课,由于时间紧张,原本就想混过去算了,但是不料考试的时候有40%的题目是计算时间复杂度的,干脆...
  • 数据结构的核心思想是通过数据结构的思维来优化代码的算法,以此来提升程序的执行性能,缩短程序执行的时间。下面我来举两个例子,以此来说明数据结构的时间复杂度计算问题。
  • 3.时间复杂度计算  以上题为例,将f(x)=f(x-1)+x/(4**x)展开, 将f(x)乘以4相减,得 ,设4的x方等于k,则原式时间复杂度 ,log以4为底。 参考: http://blog.csdn.net/budapest/article/details/6367973 /**********...
  • 常见时间复杂度计算举例1.例子2.冒泡排序时间复杂度3.二分查找的时间复杂度4.递归的时间复杂度三、空间复杂度1.空间复杂度概念2.空间复杂度的计算(1) 冒泡排序(2) 斐波那契数列(3)递归总结 一、算法效率 算法效率...
  • 复杂度 复杂度有两个维度: 时间复杂度:快慢 空间复杂度:内存占用情况...复杂度计算使用大O渐进法 常见的时间复杂度有 O(1) O(log(n)) O(n) O(n^2) O(2^n) 递归是O(2^n) 控建复杂度则需要计算调用栈 ...
  • 前提推导 log2(n) = log2(a) * loga(n) 其中 a 为常数 ----> log2(n)≈loga(n) 所以和底数已经没有关系,可直接写成 logn 大 O 表示法 是一个粗略的表示,省略掉常数,系数,低阶数 示例 public static void test1...
  • 算法时间复杂度计算公式

    千次阅读 2019-03-17 22:17:30
    那么一般都是考虑时间复杂度,下面的文章就是主要讲时间复杂度的,还有就是通过离散数学及其应用这本书来获取更多的关于算法复杂度的内容了,此文提供科普。 https://www.cnblogs.com/fanchangfa/p/3868696.ht...
  • 4.嵌套循环时间复杂度计算翻译自: https://hackernoon.com/how-we-reduced-the-time-complexity-from-18-days-to-4-5-minutes-a4bdfa72e5234.嵌套循环时间复杂度计算
  • 算法的时间复杂度 定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。...在计算渐近时间复杂度时,可以只考虑对算法运行时间贡献大的语句...
  • 二分法查找时间复杂度计算

    千次阅读 2017-09-26 16:07:51
    查找数据长度为N,每次查找后减半, 第一次 N/2 ... 第k次 N/2^k 最坏的情况下第k次才找到,此时只剩一个数据,长度为1。 即 N/2^k = 1 查找次数 k=log(N)。
  • 结果三、时间复杂度介绍四、计算时间复杂度的方法1.方法2.示例五、时间复杂度分析1.分析算法中的时间复杂度2.结果六、常见的时间复杂度1.常数阶O(1)2.对数阶O(log~2~n)3.线性阶O(n)4.线性对数阶O(nlog~2~n)5.平方阶O...
  • java时间复杂度

    千次阅读 2018-12-17 14:09:26
    O(1)是常量级时间复杂度的一种表示方法,并非只执行一行代码 代码执行时间不是随着n的增大而增大,这样的代码的时间复杂度都是O(1) 通常只要算法中不存在循环、递归,即使代码有很多行,时间复杂度仍是O(1)   ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 263,918
精华内容 105,567
关键字:

java复杂度如何计算

java 订阅