Java 数组的length方法对时间复杂度的影响问题 |
您所在的位置：网站首页 › java获得数组长度 › Java 数组的length方法对时间复杂度的影响问题 |
Java 数组的length方法对时间复杂度的影响问题
|
最近无意中看到一个问题，提到循环数组时，是否在循环体中使用length会影响时间复杂度。由于看了没保存，现在找不到在哪了，大概意思就如下面的代码。只记得这个问题是基于C语言提出的，所以我很好奇java语言中，是否存在这种问题。 int[] num = {9,3,1,2,7}; //这种写法，每次循环都要获取num.length，而获取num.length就要去遍历num，这样就会造成O(N^2)的时间复杂度 for(int i = 0; i < num.length; i++){ ... } //所以要使用下面的写法 int len = num.length; for(int i = 0; i < len; i++){ ... }正好最近有时间，就深入的去思考了一下这个问题，最开始我没有去深入思考，也是持肯定态度的，但经过我逐步的去测试，慢慢的否定了这个看法。 首先数组长度是不可变的，在内存中开辟的空间是固定的，如果我是java语言的设计者，要获取数组长度的length属性，肯定是在数组创建时就将内存空间赋给它即可，何须遍历一说。 而且如String等类的length()方法都是直接返回的数组长度，所以关键只在于这个length。既然length是java数组的关键字，那么就可以通过javap反汇编来观察。 写一个测试类Test.java package test; public class Test { public static void main(String args[]) { int[] nums = {9,3,1,2,7}; int l = nums.length; System.out.println(l); } }编译后，通过javap -c得到了它的反汇编代码，由于汇编代码我也不是很懂，具体指令我也是逐步去查看JVM指令集来参考对照看的，我给部分代码加上了有些中文注释，关键是27位置的arraylength，用于返回数组长度。可以看得出来其实JVM是通过一个arrlength执行来得到当前数组的数组长度。 有需要查看JVM指令集的可以看这篇博客：https://blog.csdn.net/tanggao1314/article/details/53260891 Compiled from "Test.java" public class test.Test { public test.Test(); Code: 0: aload_0 1: invokespecial #1 // Method java/lang/Object."":()V 4: return public static void main(java.lang.String[]); Code: 0: iconst_5 //将int型5推送至栈顶，这里的5明显就是数组的长度 1: newarray int //创建一个指定原始类型（如int, float, char…）的数组，并将其引用值压入栈顶 3: dup //复制栈顶数值并将复制值压入栈顶 4: iconst_0 //下面这些操作就是通过iastore将数组和下标分别入栈 5: bipush 9 7: iastore 8: dup 9: iconst_1 10: iconst_3 11: iastore 12: dup 13: iconst_2 14: iconst_1 15: iastore 16: dup 17: iconst_3 18: iconst_2 19: iastore 20: dup 21: iconst_4 22: bipush 7 24: iastore 25: astore_1 //将栈顶引用型数值存入第二个本地变量 26: aload_1 //将第二个int型本地变量推送至栈顶 27: arraylength //获得数组的长度值并压入栈顶 28: istore_2 //将栈顶int型数值存入第三个本地变量 29: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream; 32: iload_2 33: invokevirtual #3 // Method java/io/PrintStream.println:(I)V 36: return }所以现在我要知道的是JVM是如何通过arraylength获取到数组长度的？于是通过搜索引擎，最终又找到了这篇博客：https://blog.csdn.net/scjava/article/details/108219216 这篇博客中已经讲的很清楚了，JVM也是通过计算数组首位置+偏移量来得到数组的长度，这属于常数级的时间复杂度。看到这里是不是顿时感觉很熟悉！！！没错，在学习基础课程数据结构时，基本上都会讲过数组长度的计算，通常都是一个偏移量来确定数组在内存中的位置，这也是为什么数组的读取属于常数级别。 所以我得到的结论是：在循环体中使用num.length并不会增加时间复杂度。 jdk8的hotspot JVM源码下载地址：http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509，点击左侧zip即可下载压缩包。
|
【本文地址】
今日新闻 |
推荐新闻 |