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

问题描述

什么是声明大小为n的Java中的数组的运行时间？我想这将取决于内存是否zero'ed出来的垃圾收集（在这种情况下，它可能是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];
  }

}

字节code产生的是：

The bytecode generated is:

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

}

该指令，看看是<一个href=\"http://java.sun.com/docs/books/jvms/second_edition/html/Instructions2.doc10.html\"><$c$c>newarray指令（只需搜索 newarray ）。从虚拟机规格：

一个新的数组，其组件类型atype的和长度计数是从垃圾回收堆分配。数组引用到这个新的数组对象的引用压入操作数栈。 每个新的数组中的元素被初始化为默认初值为数组类型（§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.

修改

寻找在所提供的链接阿米特，能够实现阵列初始化具有缺省值，在一定的时间。所以我想这最终取决于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屋！