c - 如何在C中并行填充数组

Question

我需要一种算法，可以在 log(n) 时间内并行地用相同的值填充数组(大小为 n)。这意味着简单的解决方案是 for(i=0;i<=n-1;i++) T[i] = 10还不够，因为它需要 O(n)时间，我需要一些可能需要 O(log(n)) 的东西。我提到这要并行完成，这一点非常重要。我正在考虑依赖性，但我似乎无法弄清楚。

Answer 1

就像这个简单的循环一样，有多种方法可以让自己感到困惑

for (i = 0; i <= (SIZE / 2); i++) {
    arr[i]=10;
    arr[SIZE-(i+1)]=10;
}

这只会让你觉得它是 o(n/2)，但实际上你必须将值 n 次写入内存。因此，无论采取哪种方式，您最终都会执行赋值操作n次。