algorithm - 使用多个 CPU 找到最大数量的最短时间

Question

例如，假设有 32 个数字（未排序，范围未知）和 8 个 CPU，每个 CPU 每分钟计算一次比较。

如果只有一个 CPU，则需要进行 31 次比较。但是使用 8 个 CPU，我们每分钟可以比较 16 个数字。

计算最大数量所需的最少时间（以分钟为单位）是多少？（我计算出来大约需要 6 分钟，但我认为可以在 5 分钟内完成，不确定算法是如何工作的。）

Answer 1

1) 32 numbers -> compare 8 pairs using 8 CPUs -> 24 numbers
2) 24 numbers -> compare 8 pairs using 8 CPUs -> 16 numbers
3) 16 numbers -> compare 8 pairs using 8 CPUs -> 8 numbers
4) 8 numbers  -> compare 4 pairs using 4 CPUs -> 4 numbers
5) 4 numbers  -> compare all numbers with each other using 6 CPUs (tetrahedron)

Answer 2

（已编辑）第 4 步很简单

1. 比较 8 对（16 个号码）-> 8 个获胜者1
2. 比较 8 对（16 个号码）-> 8 个获胜者2
3. 比较 8 对 (8-winner1 vs 8-winner2) -> 8 个获胜者，

4. 比较 4 对 -> 4 个获胜者

   可以说4个数字是a, b, c, d

5. 比较 6 对 (a,b) (a,c) (a,d) (b,c) (b,d) (c,d) -> 最大的数字将赢得 3 次

Answer 3

把它想象成一个 NCAA Bracket，你让每个核心每分钟处理一场比赛。加上最后 4 个的四面体逻辑，你可以节省 1 分钟。