誰能幫我找到大THETA運行時間複雜度

Question

我是新來的大西塔的概念（Θ）運行時的複雜性，

我有以下的遞推關係來分析，

T（N）= 2T（N/3）+ 5N和我Θ（）

T（N）= T（N/4）+ N和我Θ（N ）

請覈實我的答案。

Answer 1

這些都是正確的。因爲每個遞歸方程的第二項比第一項高得多，所以它將在第一項中佔優勢（按照外行的說法）。

Answer 2

你的回答是正確的。 你可以通過應用主定理來解決這些問題。

的Link是至主定理，

http://en.wikipedia.org/wiki/Master_theorem#Generic_form

如果T（N）=一個T（N/B）+ F（N）其中a> = 1且b> 1

我們需要考慮的情況下，主定理3，

案例3：如果F（N）=Θ（N ^ç）其中C>登錄 _b一個

然後T（N）=Θ（N ^Ç）

首先復發

T（N）= 2T（N/3 ）+ 5N

A = 2，b = 3，F（N）= 5 N 2

那裏，F（N）=Θ（N ^Ç），其中c = 2

現在C>登錄 _b一個自2>登錄 2.

因此T（n）=Θ（n ）正如你所提到的那樣。

二復發

T（N）= T（N/4）+ N

A = 1，B = 4，F（N）= N

那裏，F（N）=Θ（N ^ç），其中c = 4。

現在C>登錄 _b一個自4>登錄因此T（N）=Θ（N ），如通過你提到 1.

。