假设为了完成某项任务n次,计算机使用了相对低效的算法。进一步假设相反,计算机开始随机选择不同的算法来执行相同的任务,所有这些算法都比我们的算法更有效。当 n 变化时,尽管效率低下,还是坚持使用该算法会更有效,还是在高效算法中随机选择会更有效?或者,这可能取决于具体情况,比如选择算法的随机性?
我已经简要阅读了有关随机计算的内容,但是我未能成功找到与此问题相关的论文。
好吧,让我们暂时抛弃“随机”的想法,因为它与您要问的内容完全无关。让我们假设有 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)
性就不再重要。
O(n^2)
,但并行(或等待足够长的时间后)它会执行类似合并排序的操作,最坏情况时间为O(n log n)
。结果具有快速排序的潜在常数因子优势,同时对于足够大的问题不会表现出二次时间。