Java：声明一个大小为n的数组的大时间是什么？
在Java中声明大小为n的数组的运行时间是多少？ 我想这将取决于内存是否在垃圾收集（在这种情况下可能是O（1））或初始化（在这种情况下它必须是O（n））归零。
这是O(n) 。 考虑这个简单的程序：
public class ArrayTest { public static void main(String[] args) { int[] var = new int[5]; } }
生成的字节码是：
Compiled from "ArrayTest.java" public class ArrayTest extends java.lang.Object{ public ArrayTest(); 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 1: newarray int 3: astore_1 4: return }
要查看的指令是newarray指令（只是搜索newarray ）。 来自VM规范：
从垃圾收集堆中分配一个新数组，其组件类型为atype，长度为count。 此新数组对象的引用arrayref被推入操作数堆栈。 新数组的每个元素都初始化为数组类型的默认初始值（第2.5.1节）。
由于每个元素都被初始化，因此需要O(n)时间。
编辑
查看提供的链接amit，可以在常量时间内使用默认值实现数组初始化。 所以我猜它最终取决于JVM。 你可以做一些粗略的基准测试，看看是否是这种情况。
关于JRE1.6的小型非专业基准测试：
public static void main(String[] args) { long start = System.nanoTime(); int[] x = new int[50]; long smallArray = System.nanoTime(); int[] m = new int[1000000]; long bigArray = System.nanoTime(); System.out.println("big:" + new Long( bigArray - smallArray)); System.out.println("small:" + new Long( smallArray - start)); }
给出了以下结果：
big:6133612 small:6159
所以我假设O（n）。 当然，这还不够确定，但这是一个提示。
我很确定它是O（n），因为在分配数组时内存被初始化。 它不应该高于O（n），我看不到让它小于O（n），所以这似乎是唯一的选择。
为了进一步说明，Java在分配时初始化数组。 如果没有走过它就无法将内存区域归零，并且区域的大小决定了指令的数量。 因此，下限是O（n）。 此外，使用比线性慢的归零算法是没有意义的，因为存在线性解，因此上限必须是O（n）。 因此，O（n）是唯一有意义的答案。
但是，只是为了好玩，想象一个奇怪的硬件，操作系统可以控制各个内存区域的电源，并可以通过关闭电源然后再打开来使区域归零。 这似乎是O（1）。 但是一个区域只能在实用程序消失之前变得如此之大（不想丢失所有东西），所以要求将区域归零仍然是具有大除数的O（n）。
我们来试试吧。
class ArrayAlloc { static long alloc(int n) { long start = System.nanoTime(); long[] var = new long[n]; long total = System.nanoTime() - start; var[n/2] = 8; return total; } public static void main(String[] args) { for(int i=1; i<100000000; i+=1000000) { System.out.println(i + "," + alloc(i)); } } }
我的linux笔记本电脑上的结果（i7-4600M @ 2.90GHz）：
因此它显然看起来像O(n) ，但它看起来也像是在大约500万个元素上切换到更有效的方法。