最近遞歸找到max的時間複雜度是多少

我只是想確保我正朝着正確的方向前進。我想通過遞歸分割找到數組的最大值，並找到每個單獨數組的最大值。因爲我分裂它，它會是2 * T（n/2）。而且因爲我必須對2個數組做最後的比較，所以我有T（1）。所以將我的遞推關係是這樣的：最近遞歸找到max的時間複雜度是多少

T = {2 * T（N/2）+ 1，當n> = 2; T（1），當n = 1;

因此，我的複雜性是Theta（nlgn）？

來源

2011-04-26 Dan

您編寫的公式似乎是正確的，但您的分析並不完美。

T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...

對於第i次迭代，你會得到：

Ti(n) = 2^i*T(n/2^i) + i

現在你想知道我做N/2^i等於1（或幾乎任何恆定的，如果有什麼你喜歡），所以你達到n = 1的最終條件。這將是解決方案n/2^I = 1 - > I = Log2（n）。植物它方程鈦在，你會得到：

TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)

，你會得到T（N）= O（N + LOG 2（N）（就像@bdares說）= O（N）（就像@ bdares說）

來源

2011-04-26 09:15:20 Neowizard

感謝您的澄清 – Dan 2011-04-26 09:31:28

寫O（n + log（n））是否正常？看起來像O（n）就足夠了，在* every *事件中。事實上，爲什麼要像這樣軟球呢？我覺得寫O（n + log（n）），雖然沒有錯，但很愚蠢。我們不爲Bubblesort寫O（n^2 + n）。我錯過了什麼嗎？如果你只是用於說明目的，那麼確定;我想對我來說有點不可思議，因爲我沒有看到最後一步......所以如果是這樣的話，只要把它當作批評風格而不是內容。 – Patrick87 2011-10-21 16:11:40

@bdares你說得對。我應該添加最後一步。爲避免混淆，我避免跳過（n + log（n））部分，但我應該確保添加最後一部分。 – Neowizard 2011-10-22 06:39:11

不，不...您每次遞歸都需要O（1）次。

有幾個？

有N片葉子，所以你知道它至少是O（N）。

你需要比較幾個才能找到絕對最大值？那是O（log（N））。

把它們加在一起，不要繁殖。 O（N + log（N））是你的時間複雜度。

來源

2011-04-26 08:51:11 bdares

哦，我看到了，我有點困惑，因爲它看起來類似於合併排序，所以是復發關係對還是錯？ – Dan 2011-04-26 08:57:28

呃..我真的很模糊，但它看起來是正確的。水平將加1，然後2，然後4，然後8，等等...所以我錯了，每步需要1 + 2 + 4 + 8 + ... + 2^log（n）時間，因此將花費O（2 * n）時間，這是O（n）時間。順便說一句，與O（N + log（N））相同也是O（n），但第一種解釋是錯誤的。 – bdares 2011-04-26 09:12:29

最近遞歸找到max的時間複雜度是多少

回答

相關問題