java - JAVA中以下方法声明、实例化和初始化数组的时间复杂度有什么区别吗？

Question

我正在学习有关数据结构和算法的在线类(class)。在那门类(class)中，老师讲了以下几种方式的时间复杂度是不同的。

方法一:

 Declare:

                int arr[]------------>O(1)

 Instantiation:

                arr = new int[size]------>O(1)


 Initialization:
               arr[0]=0;------------>O(1)
                                     -------------->O(n)
               arr[1]=1;------------>O(1)

方法2:

 Declaration,instantiation and initialization:

               int arr[]={10,20,30}---------------->O(1)

我需要知道按照第二种方法我们可以优化我们的程序，以及如何才能知道它具有 O(1) ，这两种方法之间有什么区别。

我的意思是，我认为虽然第二种方法的步骤较少，但它内部遵循第一种方法中的所有步骤，所以它不可能是O(1)，它也是O(n)，我对吗？

Answer 1

Java 的数组初始值设定项语法只是分配数组并为每个元素赋值的指令的语法糖。

这可以通过以下代码轻松验证:

import java.io.IOException;
import java.nio.file.Paths;

public class ArrayInitializer {
    public void form1() {
        int arr[] = new int[3];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
    }

    public void form2() {
      int arr[] = { 10, 20, 30 };
    }

    public static void main(String[] args) throws Exception {
        decompile();
    }

    private static void decompile() throws InterruptedException, IOException
    {
      new ProcessBuilder(Paths.get(System.getProperty("java.home"))
          .getParent().resolve(Paths.get("bin", "javap")).normalize().toString(),
          "-c", "-cp", System.getProperty("java.class.path"),
          ArrayInitializer.class.getName())
      .inheritIO()
      .start().waitFor();
    }

    private ArrayInitializer() {}
}

打印内容

Compiled from "ArrayInitializer.java"
public class ArrayInitializer {
  public void form1();
    Code:
       0: iconst_3
       1: newarray       int
       3: astore_1
       4: aload_1
       5: iconst_0
       6: bipush        10
       8: iastore
       9: aload_1
      10: iconst_1
      11: bipush        20
      13: iastore
      14: aload_1
      15: iconst_2
      16: bipush        30
      18: iastore
      19: return

  public void form2();
    Code:
       0: iconst_3
       1: newarray       int
       3: dup
       4: iconst_0
       5: bipush        10
       7: iastore
       8: dup
       9: iconst_1
      10: bipush        20
      12: iastore
      13: dup
      14: iconst_2
      15: bipush        30
      17: iastore
      18: astore_1
      19: return

  public static void main(java.lang.String[])  throws java.lang.Exception;
    Code:
       0: invokestatic  #22                 // Method decompile:()V
       3: return
}

因此，如果编译后的代码没有差异，则不会因源代码的形式而导致性能差异。

这并不排除 JVM 进行的运行时优化，例如当它检测到这是一个分配，然后填充其评估不会以泄漏未初始化数组的方式失败的值时。但这些优化在任何一种情况下都适用，因为源代码形式并不重要。

this article 中讨论了一个实际示例。关于集合的 toArray 方法，其性能取决于 JVM 识别数组分配的能力，该数组分配后立即进行复制操作，覆盖整个创建的数组。