我需要一种算法,可以在 log(n) 时间内并行地用相同的值填充数组(大小为 n)。这意味着简单的解决方案是 for(i=0;i<=n-1;i++)
T[i] = 10
还不够,因为它需要 O(n)
时间,我需要一些可能需要 O(log(n))
的东西。我提到这要并行完成,这一点非常重要。我正在考虑依赖性,但我似乎无法弄清楚。
最佳答案
就像这个简单的循环一样,有多种方法可以让自己感到困惑
for (i = 0; i <= (SIZE / 2); i++) {
arr[i]=10;
arr[SIZE-(i+1)]=10;
}
这只会让你觉得它是 o(n/2),但实际上你必须将值 n
次写入内存。因此,无论采取哪种方式,您最终都会执行赋值操作n
次。
关于c - 如何在C中并行填充数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13183414/