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

go评论63阅读模式

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，依此类推...
}
``````

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

> [...] 新数组的每个元素都被初始化为数组类型的元素类型的默认初始值（§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:
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
}
``````

``````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;
}
}
``````

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:
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

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.

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

go 58

go 73

go 51