Java：声明一个大小为 n 的数组的大 O 时间是多少？

arrays performance java complexity-theory

2022-09-01 03:55:37

在 Java 中声明大小为 n 的数组的运行时间是多少？我想这将取决于内存是在垃圾回收中归零（在这种情况下，它可能是O（1））还是初始化（在这种情况下，它必须是O（n））。

答案 1

它。考虑这个简单的程序：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."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_5
   1:   newarray int
   3:   astore_1
   4:   return

}

要查看的指令是 newarray 指令（只需搜索）。从虚拟机规范：newarray

从垃圾回收堆中分配一个新数组，其组件的类型为 atype 且长度计数。指向此新数组对象的引用数组引用将推送到操作数堆栈中。新数组的每个元素都初始化为数组类型的默认初始值（§2.5.1）。

由于每个元素都在初始化，因此需要时间。O(n)

编辑

查看提供的链接 amit，可以在常量时间内使用默认值实现数组初始化。所以我想这最终取决于JVM。您可以进行一些粗略的基准测试，看看是否属于这种情况。

答案 2

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）。当然，这还不够确定，但这是一个暗示。