大輸入的要點是什麼？

Question

在Google Code Jam中，如果您能夠解決大輸入問題，它會爲您提供2倍甚至3倍的解決小輸入點的問題。

但是，我不明白這一點。如果你製作了一個可以處理任何正數案例的程序，它可以處理10個以及10000個輸入案例。

所以，當你解決小輸入的問題時，你應該能夠解決大輸入問題，而不需要更改任何代碼。

我錯過了什麼嗎？

Answer 1

我錯過了什麼嗎？

是的 - 你錯過了時間限制。通常，對於小輸入（例如，O(n^2)算法或甚至O(2^N)算法）工作正常的算法在較大的輸入上花費太長時間，需要實質上不同的方法。

例如，尋找最長上升子序列的O(N^2)方法可以用四行代碼與單個陣列進行編碼，並且對於數百個項目的輸入它可以很好地工作。然而，這種方法會失敗的成千上萬的項目，需要一個先進的方法，使用樹或二進制搜索。由於這種不同的方法需要更長的時間進行編碼，因此用更多的積分來獎勵它是很自然的。

Answer 2

這兩個輸入可以在這些領域有所不同：

1. 問題輸入限制 例如，也許可以解決使用與O(n^2)複雜的算法有問題的小投入，但你應該解決大輸入使用更復雜的O(log n)算法。

2. 測試用例的數量 這在選擇算法時也很重要。

3. 的測試用例 硬度通常情況下，大的輸入有困難的測試情況下，如邊界條件等

Answer 3

你錯在那裏。編程語言使用特定的數據類型來存儲數據。許多數據類型通常不能保存大數據值。所以你需要修改你的代碼來合併這些大數據值。

例如，如果你使用的是C打印Fibonacci數，那麼你有一個簡單的代碼 這樣，

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中的數據類型的不足的對於需要實現自己的數據結構的解決方案。

Answer 4

Google Code Jam之間的差異小&大輸入不主要是個案數量。實際上，較大的輸入可能有小於的情況。但是，大量投入的情況比較困難。 （這通常意味着更大，這就解釋了名稱）如果您有兩倍的輸入數量，則可能需要兩倍的時間才能找到解決方案，這可能不成問題。但是如果投入更難兩次，則可能需要兩倍多的時間。