随机计算效率

Question

假设为了完成某项任务n次，计算机使用了相对低效的算法。进一步假设相反，计算机开始随机选择不同的算法来执行相同的任务，所有这些算法都比我们的算法更有效。当 n 变化时，尽管效率低下，还是坚持使用该算法会更有效，还是在高效算法中随机选择会更有效？或者，这可能取决于具体情况，比如选择算法的随机性？

我已经简要阅读了有关随机计算的内容，但是我未能成功找到与此问题相关的论文。

Answer 1

好吧，让我们暂时抛弃“随机”的想法，因为它与您要问的内容完全无关。让我们假设有 N 个可用算法来解决问题，每个算法都有不同的渐近运行时间：算法

i

在

O(f_i(x))

中运行。假设有 N 个问题需要解决，并且计算机使用不同的算法处理每个问题。

总运行时间是

O(f_1(x) + f_2(x) + ... + f_N(x)

，当然，这相当于最大时间限制。因此，如果其中大部分都是

O(log n)

并且其中只有一个

O(n^2)

，哎呀！现在您的总时间，也就是您的平均时间，是

O(n^2)

。

再加上“随机”和“预期”之类的词，结果是一样的。你的速度取决于你做的最慢的事情。

但是。考虑一种不同的方法，您需要解决一个问题，然后针对同一问题运行“所有”算法，让每个算法执行第一个操作，然后让每个算法执行第二个操作，等等，并行而不是比串行。当其中一项完成时，您可以取消其他项。 最终的时间是所有算法中的“最小值”！因此，在前一种情况下，一旦其中一个

O(log n)

算法完成（假设常数因子足够合理，它们在该问题上实际上更快），该算法的 O(n^2) 性就不再重要。

这实际上就是“introsort”算法的工作原理。它执行快速排序，在大多数实现中，最坏情况时间为

O(n^2)

，但并行（或等待足够长的时间后）它会执行类似合并排序的操作，最坏情况时间为

O(n log n)

。结果具有快速排序的潜在常数因子优势，同时对于足够大的问题不会表现出二次时间。