Kiedy można zastosować twierdzenie magisterskie?

Jestem dość sfrustrowany.Kiedy można zastosować twierdzenie magisterskie?

W CLR 3rd edition, strona 95 (rozdział 4.5), wspomina, że nawroty jak

T(n) = 2T(n/2) + n lg n

nie może być rozwiązany z Master twierdzenia, ponieważ różnica

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

jest nie wielomian.

Ale wtedy natknąłem się na strony takie jak this, gdzie na dole strony wspomniano o tym samym powtórzeniu i mówię, że MOŻNA go rozwiązać za pomocą Twierdzenia Mistrza, ponieważ wpada w "rozszerzony przypadek 2" nawet choć różnica nie jest wielomianowa. Staje się n lg^2 n (zwiększając współczynnik logu o f(n) o jeden).

Potem natknąć stron jak this gdzie w przykładzie (e) wydaje się jasny stosowania rozszerzonych przypadku 2 (nawrót jest T(n) = 4T(n/2) + n^2 lg n), ale to rozwiązanie nie jest n^2 log^2 n, ale raczej n^2 log n! Czy jestem w błędzie, czy papier jest niewłaściwy?

Czy ktoś może wyjaśnić sprzeczności i wyjaśnić dokładnie, kiedy można wykorzystać Twierdzenie Mistrza, a kiedy nie? Kiedy sprawdzanie różnicy wielomianów ma znaczenie, a kiedy nie? Czy rozszerzony przypadek 2 jest użyteczny, czy faktycznie coś narusza?

EDIT:

Próbowałem rozwiązywania nawrotów (E) bezpośrednio od drugiego papieru i uzyskać:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

Czy to nie wielki theta n^2 lg^2 n?

Źródło

2016-01-03 Aruka J

Należy zauważyć, że przypadek 2 twierdzenia głównego w książce różni się od uogólnionego formularza, który można spotkać gdzie indziej (w tym przykłady). Skąd się wzięła uogólniona forma? Ćwiczenie 4.6-2 w książce, w rzeczywistości dość łatwo udowodnić to samemu. :-) –

@MichaelFoukarakis Czy powiedziałbyś, że reguła różnicy wielomianów dotyczy tylko przypadków 1 i 3? –

"Zasada" wielomianowej różnicy jest bardziej rygorystycznym stwierdzeniem niż przypadek polilogarytmiczny. Obowiązuje we wszystkich 3 przypadkach. W przypadku # 2 można po prostu odprężyć się. –

Książka wskazuje, że nie można rozwiązać za pomocą Case 3:

chociaż wydaje się, że właściwą formę ... Może błędnie sądzi, że sprawa 3 powinno stosować

Jednak tę formułę rekurencji można rozwiązać za pomocą głównego twierdzenia, przypadek 2.

T(n) = 2T(n/2) + nlgn:

Definiujemy:

a = 2, b = 2, f(n) = nlgn

Korzystanie Master theorem case 2:

c = log_2(2) = 1 
k = 1

f(n) I rzeczywiście w Theta(nlogn).

Tak, wszystkie warunki do opanowania tw przypadku 2 stosuje się, a my możemy wywnioskować:

T(n) jest Theta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)

długie opowiadanie, Mistrz twierdzenie mają 3 przypadki. Każdy przypadek ma wymagania wstępne do zastosowania. Przypadek 3 ma bardziej skomplikowane wymagania wstępne, ponieważ wymaga również konwergencji. Ponieważ wymagania wstępne dla przypadku 3 nie mają zastosowania dla tej formuły, nie można użyć przypadku 3. Jednak wymagania wstępne przypadku 2 - mają zastosowanie i można z nich korzystać.

Źródło

2016-01-03 18:46:01 amit

Wspomina, że Przypadek 3 nie ma zastosowania, ale kilka linii przed tym, jak twierdzi, że Twierdzenie podstawowe jako całość nie ma do niego zastosowania ("Główna metoda nie ma zastosowania do powtarzania ..."), a następnie wkrótce następnie mówi: "Możesz błędnie pomyśleć, że przypadek 3 powinien mieć zastosowanie ...". Na stronie 96 stwierdza się, że wznowienie "wpada w lukę między przypadkiem 2 a przypadkiem 3". Czy książka jest zła? –

Co powiesz na to: Czy zgodziłbyś się z następującymi stwierdzeniami: CLRS jest błędne, przypadek Twierdzenia głównego 2 odnosi się do 'T (n) = 2T (n/2) + n lg n' i ma dużą Theta' n lg^2 n ', drugi papier, który połączyłem jest błędny i' T (n) = 4T (n/2) + n^2 lg n' to także przypadek 2, dlatego duża Theta 'n^2 lg^2 n' i" różnica wielomianowa "pojęcie ma zastosowanie tylko w przypadku przypadków 1 i 3? –

(1) CLRS nie określa, że nie jest to przypadek 2, faktycznie wskazuje na dowód przypadku 2 jako rozwiązanie tego problemu. Zgadzam się jednak, że frazowanie w tej książce jest nieco mylące. (2) Tylko przypadek 3 wymaga "różnicy wielomianowej", przypadku 1 i przypadku 2 nie. – amit

Kiedy można zastosować twierdzenie magisterskie?

Odpowiedz

Powiązane problemy