algorithm - 大输入有什么意义？

Question

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

但是，我不明白这一点。如果您制作一个可以处理任意正数案例的程序，它可以处理 10 和 10000 个输入案例。

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

我错过了什么吗？

Answer 1

我错过了什么吗？

是的 - 你错过了时间限制。通常，一种适用于小输入的算法（例如，O(n^2)算法甚至O(2^N)算法）在较大的输入上花费的时间太长，需要采用截然不同的方法。

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

Answer 2

Google Code Jam 小型和大型输入之间的区别主要不在于案例数量。实际上，大输入的案例可能比小输入少。但是大输入的情况更难。（这通常意味着更大，这解释了名称）如果您有两倍的输入数量，您可能需要两倍的时间才能找到解决方案，这可能不是问题。但是，如果输入的难度增加一倍，您可能需要两倍以上的时间。

Answer 3

这两个输入在这些字段中可能不同：

1. 问题输入限制 例如，也许您可​​以使用具有复杂性的算法来解决问题的小输入O(n^2)，但您应该使用具有复杂性的更好算法来解决大输入O(log n)。

2. 测试用例的数量 这在选择算法时也很重要。

3. 测试用例 的难度通常较大的输入具有更难的测试用例，例如边界条件等。

Answer 4

你错了。编程语言使用特定的数据类型来存储数据。很多时候，数据类型将无法保存大数据值。因此，您需要修改代码以合并这些大数据值。

例如，如果您使用 C 打印斐波那契数，那么您有一个简单的代码，如下所示，

long int first,second,third;
first=1;
second=1;
ct=0;
while(ct < Limit)
{
   third=first + second;
   first = second;
   second = third;
   printf("\n%d",third);
   ct++;
}

此代码是正确的，但如果斐波那契数 > 2 ³²（如果Limit非常大，则会发生），您将得到不正确的结果，因为int并且long int在 C 中是 4 个字节（32 位）。

因此，由于 C 中数据类型的不足，您的正确算法会失败。对于解决方案，您需要实现自己的数据结构。