这个问题需要一些设置。
http://igoro.com/archive/big-oh-in-the-parallel-world/
此链接中的“方法 1”详细介绍了用于描述并行性对算法时间复杂度的影响的符号。我真的很喜欢这种描述方法，但这是我唯一找到的地方。
我的问题如下:为什么这个符号没有被更频繁地使用？
方法描述本身实际上给出了一个解释:“为了将两个 100×100 矩阵相乘，我们需要一台具有 10,000 个处理器的机器”。这句话似乎表明 10,000 个处理器对于任何人来说都是完全不合理的。
我的反驳:
https://en.wikipedia.org/wiki/Manycore_processor
目前世界上最大的 super 计算机太湖之光共有40960*256 = 10485760个内核。我们并不都拥有像太湖之光这样的 super 计算机，但随着云计算的不断普及，我认为在不久的将来，10,000核及以上的处理器没有理由不能广泛使用。最重要的是，GPU 平均已经拥有 1000 个核心。它们比 CPU 核心更专业，但这不是重点。
由于这种表示法的示例很少，我还将使用等效的描述提供我自己的示例，我将其称为大货币表示法。
假设我们有一棵完全平衡的树，其分支因子为 b。除第一个节点外，所有节点均包含 bool 值 false，最后一个节点包含 bool 值 true。我们想要找到并返回这个真实的节点。
使用广度优先搜索，Big-O 运行时找到真正的节点将是 O(|V|+|E|) == O(b^d)，其中 b 是分支因子，d 是树的深度。
但是，如果我们假设我们有无限多个处理单元，每个处理单元的处理能力都是有限的，那么大钱符号如下:$O(b^d -> d)。这说明，在 1 个处理器上，该算法将花费 O(b^d) 时间，但随着处理器数量的增加，时间复杂度接近 d(树的深度)。这是因为在每个错误节点，我们可以生成更多 b 个进程来搜索每个节点 b 个子节点。由于我们有无限的核心，所有这些进程都可以并行工作。这就是为什么我称其为大货币符号。时间复杂度随着处理能力的增加而降低，当您在 Amazon/Microsoft/Google/YourFavoriteCloudProvider 上投入更多的钱时，处理能力也会增加。
我会再次重申我的问题。为什么与此类似的符号没有得到更广泛的使用？谢谢!
最佳答案
The complexity class NC处理可以在并行设置中有效解决的问题。据我所知，研究并行算法的人确实使用传统的O(.)表示法并使用诸如“NC算法”之类的表达式，因此当你阅读他们的论文并看到如下句子时:
“我们针对某些问题给出了 O(xxx) NC 算法。”
您应该将其解释为:
“我们为 SOMEPROBLEM 提供了一种并行算法，它使用 O(yyy) 处理器在 O(xxx) 时间内解决了该问题。”
(其中 xxx 和 yyy 当然不同)。
我不记得看到过与您的符号类似的东西，但我不确定它会带来什么。复杂性类别通常根据某些参数和/或该参数的某些增长度量进行分区(例如，我们可以访问 O(1) 处理器，或 O(log n) em> 处理器，或...)，以便以一定程度的精度对问题进行分类，如果我正确解释的话，您的符号似乎缺乏。
关于algorithm - 包含并行性的 Big-O 表示法版本？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55624555/