2@amit 使用你的公式,当 n == k 时会发生什么?n/n + log(n) = 1 + log(n) = log(n)。因此,如果你有 n 个核心(实际上 n/2 个核心就足够了),你可以获得 O(log(n))。尽管你可能需要添加一个并行化开销项(处理器之间通信的延迟)。 - Xantix
4@Xantix,@Mystical:这是一个特例,其中核心数与元素数量成线性关系。传统上,在并行分析中,我们有两种选择:(1)将k视为某个常量,因此忽略它。 (2)明确使用k符号。我从未看过任何一本书/文章分析算法时假设核心数k = f(n)为某个函数f(当然除了常数)。如果有人这样做了,请引用这个来源,我会撤回我的评论。 - amit
1@Mystical,我认为线程分配复杂度仍然是O(n),因此最终会得到O(n log n)。Brent定理可能有助于一些算法级联(证明并不简单),但也许我误解了这个概念。请参见http://www.uni-graz.at/~haasegu/Lectures/GPU_CUDA/Lit/reduction.pdf幻灯片30。 - David Titarenco
1@DavidTitarenco:我不能针对这种情况发表意见,但我知道在排序网络中,复杂度明确地被限定为“大小”(与O(#processors x time complexity)相关)或“深度”(与O(time complexity)相关),因此我会推断出对于这个问题,如果充分限定,两者都是正确的想法。http://en.wikipedia.org/wiki/Sorting_network - Mooing Duck
k > n
时。 - Mysticialk
视为某个常量,因此忽略它。 (2)明确使用k
符号。我从未看过任何一本书/文章分析算法时假设核心数k = f(n)
为某个函数f
(当然除了常数)。如果有人这样做了,请引用这个来源,我会撤回我的评论。 - amitO(n)
,因此最终会得到O(n log n)
。Brent定理可能有助于一些算法级联(证明并不简单),但也许我误解了这个概念。请参见http://www.uni-graz.at/~haasegu/Lectures/GPU_CUDA/Lit/reduction.pdf幻灯片30。 - David TitarencoO(#processors x time complexity)
相关)或“深度”(与O(time complexity)
相关),因此我会推断出对于这个问题,如果充分限定,两者都是正确的想法。http://en.wikipedia.org/wiki/Sorting_network - Mooing Duck