Java:声明大小为 n 的数组的大 O 时间是多少? [英] Java: what's the big-O time of declaring an array of size n?

问题描述

在Java中声明一个大小为n的数组的运行时间是多少?我想这将取决于内存是否在垃圾收集(在这种情况下可能是 O(1) )或初始化(在这种情况下它必须是 O(n) )时清零.

What is the running time of declaring an array of size n in Java? I suppose this would depend on whether the memory is zero'ed out on garbage collection (in which case it could be O(1) ) or on initialization (in which case it'd have to be O(n) ).

推荐答案

O(n).考虑这个简单的程序:

It's O(n). Consider this simple program:

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).来自 VM 规范:

The instruction to take a look at is the newarray instruction (just search for newarray). From the VM Spec:

从垃圾收集堆中分配一个新数组，其组件类型为 atype 且长度为 count.这个新数组对象的引用 arrayref 被推送到操作数堆栈中.新数组的每个元素都初始化为数组类型的默认初始值(第 2.5.1 节).

A new array whose components are of type atype and of length count is allocated from the garbage-collected heap. A reference arrayref to this new array object is pushed into the operand stack. Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1).

由于每个元素都被初始化，所以需要 O(n) 时间.

Since each element is being initialized, it would take O(n) time.

编辑

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

Looking at the link amit provided, it is possible to implement array-initialization with a default value, in constant time. So I guess it ultimately depends on the JVM. You could do some rough benchmarking to see if this is the case.

这篇关于Java:声明大小为 n 的数组的大 O 时间是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！