JavaScript初始化二维、三维数组：与C++/Java的时空复杂度对比

Great question! Let's break down the time/space complexity and practical performance differences between your JavaScript approach, C++'s memset, and common Java 2D array initialization methods.

1. Your JavaScript Approach: new Array(m).fill().map(() => new Array(n).fill(-1)) #

Let's start with what's happening here:

• new Array(m).fill() creates an array of length m filled with undefined — this runs in O(m) time.
• The map method iterates over each of the m elements, and for every iteration, we create a new array of length n and fill it with -1 (each new Array(n).fill(-1) is O(n) time).

Time Complexity #

Total time is O(m + m*n), which simplifies to O(mn) — since the m*n term dominates the linear m term. Every element in the 2D array is explicitly initialized once.

Space Complexity #

We're storing m separate arrays each of length n, so the total space is O(mn). There's a tiny bit of extra overhead from JavaScript's array objects (like length tracking), but this is negligible in asymptotic terms. Also, importantly, this approach avoids the common pitfall of shared subarray references, so each row is independent.

2. C++ memset for 2D Arrays #

First, a quick note: memset initializes memory byte-by-byte, so it works for setting -1 (since -1 in two's complement is all 1s in every byte) or 0, but not arbitrary integer values.

Time Complexity #

• For a contiguous 2D array (like int arr[m][n]; on the stack, or int* arr = new int[m*n];), memset(arr, -1, sizeof(arr)) runs in O(mn) time — it scans every byte of the array in one go.
• For a dynamic array of pointers (int** arr = new int*[m];), you'd need to loop through each row and call memset on it: this is still O(mn) total time, since each row's n elements are initialized individually.

While the asymptotic complexity matches JavaScript, practical runtime is much faster — memset is a highly optimized low-level function that directly manipulates memory without the overhead of object creation or function calls.

Space Complexity #

• Contiguous arrays use O(mn) space with no extra overhead (just the raw element data).
• Pointer-based dynamic arrays have a tiny extra cost for the m pointers (O(m)), but this is still dominated by the O(mn) element space.

3. Java 2D Array Initialization #

The standard way to initialize a 2D array to -1 is:

int[][] arr = new int[m][n];
for (int i = 0; i < m; i++) {
    Arrays.fill(arr[i], -1);
}

Time Complexity #

new int[m][n] creates the outer array and initializes each subarray to default 0 (O(m) time), then Arrays.fill runs O(n) per row, leading to total O(mn) time — same asymptotic complexity as JS and C++.

Space Complexity #

Java's 2D arrays are "arrays of arrays", similar to JavaScript. Total space is O(mn), with minor overhead for each subarray's metadata (like length).

Key Takeaways #

• Asymptotic Time Complexity: All three approaches are O(mn) — they all need to touch every element in the 2D array at least once.
• Practical Runtime: C++ memset > Java Arrays.fill > JavaScript map+fill — this is due to low-level memory access in C++, optimized native methods in Java, and JavaScript's higher overhead for array object creation and function callbacks.
• Space Complexity: All are O(mn). The only difference is memory layout: C++ can use contiguous memory (more cache-efficient), while JS/Java use disjoint subarrays (slight extra metadata overhead, but negligible for large arrays).

内容的提问来源于stack exchange，提问作者Rashidtvmr