證明遞歸函數的上界複雜度？

我很困惑如何使用數學歸納法證明大O的遞歸函數，給定使用它的遞歸關係。證明遞歸函數的上界複雜度？

實施例：

爲遞歸實現河內塔的遞推關係是T（N）= 2T（N-1）+ 1
和T（1）= 1，我們要求保護的這個遞歸方法是O（n）= 2n - 1。使用數學歸納證明這個說法。

在遞歸的情況下，我是否總是假定n = k-1，而不是n = k？這是講義給出的假設。

假設f（n-1）= 2 ^（n-1）-1爲真。

我知道非遞歸數學歸納法，我們假設n = k，因爲它只是變量的變化。那麼爲什麼假設n = k-1是安全的呢？

來源

2014-02-12 Jay

我會問這是Stack Exchanges [計算機科學]（https://cs.stackexchange.com/）站點，因爲它更適合那裏。 – jpw

這與Java無關。標籤已移除。 – ajb

在數學歸納中，「假設」並不是你真正假設的事實。這是一個充分條件的陳述。你希望證明的是，如果關於一個數的條件是真的，那麼它在邏輯上意味着下一個數的一個結論也是成立的。然後，你顯示條件對於第一個數字是真實的，並且與條件暗示的條件相結合，你通過在整數上無限級聯來證明結論。這就是感應的工作原理。如果某些不同的變量選擇使得數學更方便，那並不重要。 – jpmc26

一種可能的方法：假設T的非遞歸公式並證明它。之後，顯示你找到的公式在你想要的大O中。

對於證明，您可以使用歸納，在這種情況下，它是快速和容易的。爲此，您首先顯示您的公式適用於第一個值（通常爲0或1，在您的示例中爲1且不重要）。

然後你會發現，如果它適用於任何數字n - 1，它也適用於其繼任者n。爲此，您使用T(n)（在您的示例中爲T(n) = 2 T(n - 1) + 1）的定義：如您所知，您的formla適用於n - 1，則可以用公式替換T(n - 1)的出現次數。在你的榜樣，你再拿到（與式T(n) = 2^n - 1）

T(n) = 2T(n - 1) + 1 
    = 2(2^(n - 1) - 1) + 1 
    = 2^n - 2 + 1 
    = 2^n + 1

正如你所看到的，它適用於n如果我們假定它適用於n - 1。

現在來介紹誘導技巧：我們證明我們的公式適用於n = 1，並且我們證明如果它適用於任何n = k - 1，它也適用於k。也就是說，正如我們爲1所證明的那樣，它也被證明爲2。並且由於2已被證實，它也被證明爲3。因爲它是...

因此，我們並不假定n - 1這個詞在我們的證明中是正確的，我們只是在假設它是真實的情況下做了陳述，然後證明了我們的公式爲一個初始情況，並使用誘導。

來源

2014-02-12 01:06:41 dst

數學的第一步使我困惑。您可能需要添加一個額外的步驟，以顯示您正在爲像我這樣厚的頭部分發2。 =） – jpmc26

證明遞歸函數的上界複雜度？

回答

相關問題