java什么是数组的时间复杂度。parallelSetAll（）？

Question

我刚读到：Everything about java 8 因此，Java8添加了数组。parallelSetAll（）

int[] array = new int[8];
AtomicInteger i= new AtomicInteger();
Arrays.parallelSetAll(array, operand -> i.incrementAndGet());

[编辑]对于数组中相同数量的元素，同一台机器上的时间复杂度是O（1）还是常数？方法名称表明了什么样的性能改进

Answer 1

它是O(N)。调用Arrays.parallelSetAll(...)涉及到设置array.length数组元素总数的赋值。即使这些分配分布在P处理器上，分配的总数也与阵列的长度成线性比例。以N作为数组的长度，数学是显而易见的

要意识到的是P。。。可用处理器的数量。。。对于单台计算机上任何给定的程序执行，都是一个常数。（或者，如果它不是常数，则会有一个常数上限。）而一种计算，其唯一目的是为数组赋值，只有在一台计算机上执行时才有意义

Answer 2

首先，它永远不可能是O（1），更多澄清如下：

我使用的是n = array.length，在你的例子中是8，但是这并不重要，因为它也可能是一个非常大的数字

现在观察一下，通常你会做：

for (int i = 0; i < n; i++) {
    array[i] = i.incrementAndGet();
}

这在Java 8中要容易得多：

Arrays.setAll(array, v -> i.incrementAndGet());

观察它们都需要O（n）时间

现在考虑到你是并行执行代码的，但是没有保证它是如何执行的，你不知道它在引擎盖下执行了多少次并行化，如果有那么少的并行化的话

因此它仍然需要O（n）个时间，因为您无法证明它将在n个线程上并行

编辑，作为一个额外的例子，我观察到，你似乎认为并行化一个动作意味着任何O（k）都将收敛到O（1），其中k = n或k = n^2，等等。
实际情况并非如此，因为您可以证明，您从来没有可用的k处理器内核

一个直观的论点是你自己的计算机，如果你幸运的话，它可能有8个核，因此在完美的并行化条件下，你能得到的最大时间是O（n/8）
我已经听到未来的人们嘲笑我们只有8个CPU核