使用數學歸納法證明覆發系統

具有FNC：使用數學歸納法證明覆發系統

bool ISINTREE(int x, BinTree<int> t) 
    { 
    bool b = false 

    if (!t.isEmpty()) 
    { 
    if (x == t.getRoot()) 
     { b = true } 
    else 
     { 
     if (ISINTREE(x,t.leftTree())) 
     { b = true } 
     if (ISINTREE(x,t.rightTree())) 
     { b = true } 
     } 
    } 

    return b 
    }

如何（使用數學歸納法），該T（N）= 11×2^N證明 - 圖7是復發系統的解決方案這個fnc。

EDITED
設F（N）= 11 * 2^N - 7
現在，
對於k> 0
T（K-1）= F（K-1）= 11 * 2（k-1）-7
T（k）= 7 + 2 *（T（k-1））
= 7 + 2 *（11 * 2 ^（k-1）-7）
= 11 * 2^k -7

來源

2011-04-08 There is nothing we can do

這是什麼n？樹中元素的數量？如果是這樣，那麼我們可以肯定地說，最壞的情況下，這個算法訪問樹中的每一個節點，所以運行時間最壞的情況是T(n) = n，在這種情況下，前提條件（即T(n) = 11 . 2^n - 7）不能有效。

UPDATE

爲了滿足懷疑，讓我們來看看在最壞的情況下（找項目不在樹）。不失一般性，讓我們假設我們正在尋找一個完美平衡的樹，即每個子樹都有(n-1)/2元素。因此，在這些假設下，復發的關係是：

T(n) = 2.T((n-1)/2) + 7

（我說的是真的只有4可執行此操作，但讓我們把它7爲簡單起見）。

顯然，T(n) = 11 . 2^n - 7不是這種關係的解決方案。

來源

2011-04-11 15:27:23

@Oli -1你的答案是不正確的。而且我想我不會從你那裏發現你錯了（在所有這些事情上），對吧？不，我當然不會。但是，請爲了將來的參考，不要以任何形式參與我的問題。 – 2011-04-13 16:18:43

@你：你給了你的解決方案。我指出了一個具體問題;我們對重複關係是什麼有不同的看法。我解釋了爲什麼我認爲你的復發關係是錯誤的。您尚未對該特定問題提出意見。如果你想進行一場長大的辯論，那麼我非常樂意。（如果你只是想告訴我，我不知道我在說什麼，同時避免具體情況，那麼我不願意......） – 2011-04-13 17:08:27

@Oli我的復發是正確的，你是誰給了錯誤的答案。不幸的是，我正在準備相當重要的考試，我真的沒有時間進行辯論，也沒有時間解釋爲什麼它是正確的。在我的考試結束後（12.VI.11），我沒有任何問題向你展示爲什麼這樣。 – 2011-04-13 18:23:50

使用數學歸納法證明覆發系統

回答

相關問題