并发世界的大O符号是否相关？

Question

在大多数流行的语言中,比如C/C++/C#/ Erlang/Java,我们有线程/进程; GPGPU计算市场正在增长.如果算法需要N个与数据无关的步骤,那么我们得到的性能就不一样,因为算法需要所有步骤都相互跟随.所以我想知道大O符号在并发世界中是否有意义？如果它与分析算法性能无关？

您可以在分布式环境中拥有N个或更多处理器(未来的GPGPU /集群/ FPGA,您可以根据需要获得尽可能多的内核 - 并发世界,不限于并行内核的数量)

Answer 1

Big-O符号仍然相关.

您有一定数量的处理器(假设),因此只能同时发生一定数量的事情,因此您只能通过常数因子加速算法,而大O则忽略常数因子.

因此,无论您是查看步骤总数,还是只考虑处理器处理大多数步骤所采取的步骤数,我们最终都会得到完全相同的时间复杂度,这最终会让我们对速率有一个不错的认识与输入大小相关的时间增长

...未来您可以根据需要获得尽可能多的内核 - 并发世界,而不仅限于并行内核的数量.

如果我们甚至可以在几秒钟内完成非常大输入的指数运行时算法运行的阶段,那么是的,big-O表示法和算法研究可能会变得不那么相关.

但是,考虑到,例如,对于O(n!)算法而言n = 1000(实际上这是相当小的),它将需要在4x10^2567步骤的区域中,这大约是整个可观察宇宙中估计的原子数量的4x10^2480倍数.简而言之,大O符号不太可能变得无关紧要.10^87

即使假设有效数量有限的处理器,我们仍然可以使用big-O表示法来指示处理器处理大多数步骤所采取的步骤(应该指示运行时间).

如果我们愿意的话,我们也可以用它来表示使用的处理器数量.

最重要的是,大O符号表示函数的增长率 - 一个可以代表任何东西的函数.仅仅因为我们通常使用它来表示算术计算的数量,步骤,比较或类似并不意味着那些是我们可以使用它的唯一的东西.