帕斯卡三角形優點

帕斯卡三角形可以被用於計算使用下面的遞歸式的組合的數目： -帕斯卡三角形優點

(n k) = (n-1 k-1) + (n-1 k)

這可以代替正式膨脹（N K）的用於計算組合的數目。但都在O（n）時間執行。使用帕斯卡三角形方法的優點是什麼？

計算帕斯卡三角形爲O完成（N^2），而不是O（N ）！ –

主要優點就在於，你可以預先計算所有(ni ki)其中ni < n和ki <= k在O(n^2)時間。

所以，如果你有問題，你可能需要在帕斯卡三角查詢不同的值，使用遞推公式法和存儲所有子結果將意味着你的預處理時間爲O(n^2)，但你的查詢都是O(1)。

在另一方面，使用(n k)公式中的同一個應用程序將意味着每個查詢是O(n)，如果你希望超過n疑問這是不如前一種方法。

2014-05-19 08:30:48 cyon

計算Pascal的三角形在O（N^2）中完成，而不是O（N）！ –

@YvesDaoust你當然是對的。固定。在預處理階段使用它的想法仍然是一樣的。 – cyon

如果您需要計算n<=N和0<=k<=N的所有(n k)，Pascal三角形非常有吸引力，因爲它只涉及每個元素的一個加法。

但是如果你只需要一個固定N的值，那麼就可以有利地使用其他遞歸：

2014-05-19 09:10:35

回答