algorithm - 大输入的意义何在？

Question

在 Google Code Jam 中，如果您能够解决大输入问题，它会给您 2 甚至 3 倍解决小输入问题的分数。

但是，我不明白这有什么意义。如果您编写的程序可以处理任意正数的案例，那么它可以处理 10 到 10000 个输入案例。

因此，当您解决小输入的问题时，您也应该能够解决大输入的问题，而无需更改任何代码。

我错过了什么吗？

Answer 1

Am I missing something?

是的 - 你错过了时间限制。通常，适用于小输入的算法(例如，O(n^2) 算法甚至 O(2^N) 算法)在更大的投入，需要截然不同的方法。

例如，寻找最长上升子序列的 O(N^2) 方法可以用一个数组编码成四行代码，并且它可以很好地处理数百个输入项目。但是，该方法对于数十万个项目将失败，需要使用树或二分搜索的高级方法。由于这种不同的方法需要更长的编码时间，因此自然会用更多的积分来奖励它。