使用仅涉及单行代码的表示法将多个元素分配给数组的时间复杂性是多少?

huangapple go评论70阅读模式
英文:

What is the time complexity of assigning multiple elements to the array using the notation that uses only a single code line?

问题

我是指这样的情况:

int[] array = {1, 2 , 3, 4, 5};

其中每个数组索引的赋值都在“单行代码中完成”。

我并不确定在背后会发生什么,但我想象中的情况是,它类似于对数组中的每个索引进行迭代,然后将输入的整数赋值给该索引:

for (int i = 0; i < array.length; i++){
    array[i] = <给定的输入>  //对于 array[1],值将为 1;array[2] 的值为 2,依此类推...
}

如果是这样的话,时间复杂度是 O(n) 对吗?
虽然再次强调,这只是我对多次对数组进行赋值的情况的假设。

英文:

I am referring to something like:

int[] array = {1, 2 , 3, 4, 5};

Where the assignment of a value to each array index is done "all in a single line of code".

I do not really know for sure what happens in the background with this,
but what I have imagined is that it's something like an iteration through each index in the array, and then assigning the inputted int to that index:

for (int i = 0; i&lt;array.length; i++){
array[i] = &lt;given input&gt;  //for array[1] the value will be 1, array[2] is 2 and so on...
}

If that is the case, it is in O(n) right?
Though again, it is just my assumption of how the multiple assignments to an array occurs.

答案1

得分: 3

非常相关,所以请查看:Java:声明大小为 n 的数组的大O时间是多少?

初始化数组的生成字节码涉及到 newarray 指令,其复杂度为 O(n),因为每个元素在进行任何其他操作之前都会被初始化为默认状态。详见:JVM 规范,第576页:

> [...] 新数组的每个元素都被初始化为数组类型的元素类型的默认初始值(§2.3,§2.4)。

此外,您在此处使用的是数组初始化器,因此让我们查看字节码:

public class Main {
	public static void main(String[] args) {
		int[] array = {1, 2 , 3, 4, 5};
	}
}

... 编译为 ...

public class Main {
  public Main();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object.&quot;&lt;init&gt;&quot;:()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: iconst_5
       1: newarray       int
       3: dup
       4: iconst_0
       5: iconst_1
       6: iastore
       7: dup
       8: iconst_1
       9: iconst_2
      10: iastore
      11: dup
      12: iconst_2
      13: iconst_3
      14: iastore
      15: dup
      16: iconst_3
      17: iconst_4
      18: iastore
      19: dup
      20: iconst_4
      21: iconst_5
      22: iastore
      23: astore_1
      24: return
}

请注意 newarray 和传递给它的 iconst_5。这属于代码中的“new int[5] 部分”,其中 iconst_5 实际上是 5(“整数常量 5”)。请忽略 dupastore_1,它们对于问题不太重要。

请注意 iconst_0iconst_1iastore 块,它们对其他整数常量重复。iastore 是将值存储到数组中的指令,其中第一个参数是索引,第二个参数是值。在 iastore 之前的两行是参数。因此,您看到的是字节码读取数组初始化器中的每个元素并将其存储在数组中。

因此,您显示的这个一行代码在字节码级别上实际上非常类似(或等效)于这个:

public class Main {
	public static void main(String[] args) {
		int[] array = new int[5];
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
	}
}

正如您所见,您显示的一行代码在字节码级别上实际上是 2 * O(n)

英文:

Very related, so check it out: Java: what's the big-O time of declaring an array of size n?

The resulting bytecode for initializing an array involves the newarray instruction, which is O(n) as each element is initialized to the default state before anything else. See: JVM Spec., page 576:

> [...] Each of the elements of the new array is initialized to the defaultinitial value (§2.3, §2.4) for the element type of the array type.

What you are using here additionally is an array initializer, so let's check out the bytecode:

public class Main {
	public static void main(String[] args) {
		int[] array = {1, 2 , 3, 4, 5};
	}
}

... is compiled to ...

public class Main {
  public Main();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object.&quot;&lt;init&gt;&quot;:()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: iconst_5
       1: newarray       int
       3: dup
       4: iconst_0
       5: iconst_1
       6: iastore
       7: dup
       8: iconst_1
       9: iconst_2
      10: iastore
      11: dup
      12: iconst_2
      13: iconst_3
      14: iastore
      15: dup
      16: iconst_3
      17: iconst_4
      18: iastore
      19: dup
      20: iconst_4
      21: iconst_5
      22: iastore
      23: astore_1
      24: return
}

Notice the newarray with iconst_5 passed to it. This belongs to the "new int[5] part" of the code, where iconst_5 is just 5 ("integer constant 5"). Ignore the dup and astore_1, they're not so important for the question.

Notice the iconst_0, iconst_1 and iastore block, which is repeated for other integer constants. iastore is the instruction to store a value in an array, where the first parameter is the index and the second parameter is the value. Two lines before the iastore are the arguments. So what you see is that the bytecode reads each of the elements in your array initializer and stores it in the array.

So what the one-liner does is actually very similar (or equivalent) to this:

public class Main {
	public static void main(String[] args) {
		int[] array = new int[5];
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
	}
}

As you can see, the one-liner you've shown is actually 2 * O(n) at bytecode-level.

答案2

得分: 1

The answer from @akuzminykh is nice and sufficient.

But what you are fishing for is compile time preparation of data.

static final String STR = "...非常长的字符串...";

This string is compiled as a UTF-8 string in the constant pool of the class. A Java String will normally hold its data as an array of UTF-16 (2-byte) chars, but the newest Java versions can hold a byte array together with an encoding of it. So assume this to be the case for our string constant.

Then still, the bytes need to be copied.
Hence for n bytes, it's still O(n). But it will be fast and (likely) on the native code side. A string of 1 character will be loaded faster than a string of 10,000 characters. But the real effect is probably not measurable, not suitable for optimization.

英文:

The answer from @akuzminykh is nice and sufficient.

But what you are fishing for is compile time preparation of data.

static final String STR = &quot;....very long string ...&quot;;

This string is compiled as UTF-8 string in the constant pool of the class. A java String will normally hold its data as array of UTF-16 (2 byte) chars, but the newest java versions can hold a byte array together with an encoding of it. So assume this to be the case for our string constant.

Then still the bytes need to be copied.
Hence for n bytes still O(n). But it will be fast and (likely) on the native code side. A string of 1 character will be loaded faster than of 10 000 characters. But the real effect probably not measurable, not apt for optimisation.

huangapple
  • 本文由 发表于 2020年10月7日 18:35:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/64242270.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定