運行時間t（n）= t（n-2）+（n-2）2

任何人都可以告訴我以下解決方案是否正確？運行時間t（n）= t（n-2）+（n-2）2

我試圖計算的T（N）= T的運行時間（n-2）+（N-2）²

進一步評估它

=> T（N ）= T（N-4）+（N-2）2 +N²

=> T（N）= T（N-6）+（N-6）2 +（N-2）² +n²

...因爲它減少2它會有一個第二n/2個術語和通過擴大所有平方我們有（N/2）*（N²）等於n³.So的運行時間是THETA（N 3）

這是正確的溶液？

來源

2012-09-22 Sid

這是更computercience.stackexchange.com問題。 –

你想計算該函數的運行時間？即如果您將該功能作爲計算機程序實現，您想知道運行時間是多少？或者你的意思是這個函數*是你的運行時間，你想知道它在哪個？ – sepp2k

是的，我想計算功能的運行時間（函數的順序） – Sid

是的，以上是完全正確的（根據問題定義，第一行的小例外應該是，並且糾正後面的內容 - 但不影響漸近結果）。

爲了證明這一點，我們可以使用mathematical induction：

Claim: t(n) <= n^3 
base: T(2) = 2 (assumption - otherwise we'll get stuck) 
let's assume the assumption is true for each n<k for a certain k. 
t(k) = t(k-2) + (k-2)^2 <= (k-2)^3 + (k-2)^2 = 
    = k^3 -6k^2 + 12k -8 + k^2 - 4k + 4 
    = k^3 -5k^2 + 8k - 4

所有剩下的就是證明5k^2 >= 8k - 4，我們就完成了。該公式適用於每個k>=2 - 證明它是作爲一個精確的。

從上面我們可以推導出t（n）在O(n^3)。使用類似的方法，我們可以顯示它也在Omega(n^3)，因此它是Theta(n^3)

來源

2012-09-22 07:36:02 amit

我做了一個小小的計算錯誤：'k^3 -5k^2 + 8k + 4'實際上應該是'k^3 -5k^2 + 8k - 4' - 它不會改變結論當然，對於每個k> = 2，公式仍然是正確的。 – amit

Using this online calculator您可以看到Θ（n^3）作爲結果。

n^3

右乘創建Θ（N^3），因爲我認爲。

來源

2012-09-22 07:35:54 FLCL

你從哪裏看到的？你需要pro-version來獲得運行時間嗎？ –

@TheUnfunCat看帖子更新 – FLCL

運行時間t（n）= t（n-2）+（n-2）2

回答

相關問題