数组内存分配的时间复杂度(非动态)

Question

如果我这样做

int n = some arbitrary number
int[] array = new int[n];

所需时间是线性(O(n))还是常数(O(1))?
我查看了javadoc和eg。这里在StackOverflow，但没有找到答案，因为所有的帖子我看到处理动态分配

Answer 1

在java中，当你创建一个新的数组int时，数组的所有成员都必须获得int的初始值(即'0')，因此初始化包括n对值0的赋值，从而占用O(n)。

您也可以使用以下代码验证它，使用不同的n:

public static void main(String[] args)
{
    int n = 1000000;
    int numSamples = 10000;
    long sumTime = 0;
    for (int i = 0; i < numSamples; i++)
    {
        sumTime += test(n);
    }
    double average = sumTime / (double) numSamples;
    System.out.println(average);
}
private static long test(int size)
{
    long start = System.currentTimeMillis();
    int[] a = new int[size];
    return System.currentTimeMillis() - start;
}