Błąd w użyciu notacji asymptotycznej

10

Usiłuję zrozumieć, co jest nie tak z następującym dowodem kolejnego wystąpienia

T(n)=2T(n2)+n
T(n)2(cn2)+ncn+n=n(c+1)=O(n)

Dokumentacja mówi, że jest błędna z powodu hipotezy indukcyjnej, że

T(n)cn
Czego mi brakuje?
Erb
źródło
2
Nawroty tej formy można również rozwiązać za pomocą twierdzenia Master .
Juho
2
@Ran: Nie sądzę, aby twierdzenie-mistrz było odpowiednim znacznikiem dla tego pytania. Pytanie nie dotyczy tego, jak go rozwiązać, ale wskazać na błąd w konkretnym argumencie. Poza tym twierdzenie mistrza jest prawdopodobnie zbyt szczegółowe i prawdopodobnie nie zasługuje na to, by mieć własny znacznik. Ogólnie rzecz biorąc, powinniśmy oznaczać na podstawie pytania, a nie możliwych odpowiedzi. Na przykład, czy oznaczyłbyś to akra-bazzi?
Aryabhata
„co jest nie tak z następującym dowodem” - nie widzę dowodu. Często pomocne jest spisanie pełnego dowodu (tj. Wyraźne wprowadzenie) w celu wykrycia błędów.
Raphael
Powiązanym bardziej ogólnym pytaniem jest rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb .
Juho

Odpowiedzi:

12

Powiedzmy, że ostatecznym celem jest udowodnienie, że . Zaczynasz od hipotezy indukcyjnej:T(n)=O(n)

dla wszystkich i < n .T(i)cii<n

Aby ukończyć dowód, musisz również wykazać, że również.T(n)cn

Można jednak wywnioskować, że , co nie jest pomocne w wypełnieniu dowodu; potrzebujesz jednej stałej c dla (prawie) wszystkich n . Dlatego nie możemy niczego wywnioskować, a T ( n ) = O ( n ) nie zostało udowodnione.T(n)(c+1)ncnT(n)=O(n)

Zauważ, że jesteś zdezorientowany między wynikiem a procesem sprawdzania. I jeszcze jeden punkt, jest w tym przypadku Θ ( n log n ), więc możesz rozważyć odpowiednią hipotezę indukcyjną, aby móc to udowodnić.T(n)Θ(nlogn)

Podkładka
źródło
jeśli zastąpimy c '= c + 1, czy spowoduje to jakąkolwiek zmianę?
Erb
@erb: Nie, nie będzie. Musisz udowodnić dla wybranej stałej. Jeśli zastępując , ostatecznie masz T ( n ) ( c + 1 ) n (lub T ( n ) ( c + 2 ) n ), to wynik jest taki sam. c=c+1T(n)(c+1)nT(n)(c+2)n
pad
8

Pominąłeś kilka kroków. Wygląda na to, że próbujesz udowodnić przez indukcję, że T(n)=O(n) , a twój dowód to:

Załóżmy, że dla k < n . Oznacza to, że T ( k ) cT(k)=O(k)k<n dla niektórych c . Następnie T ( n ) = 2 T ( n / 2 ) + n 2 c n / 2 + n ( c + 1T(k)ckc , więc T ( n ) = O ( n ) .T(n)=2T(n/2)+n2cn/2+n(c+1)nT(n)=O(n)

Ten dowód od samego początku idzie źle: „ dla k < n ” nie ma sensu. Duże oh jest pojęciem asymptotycznym: T ( k ) = O ( k ) oznacza, że ​​istnieje pewna stała c i wartość progowa N taka, że k N , T ( k ) cT(k)=O(k)k<nT(k)=O(k)c . I znowu na końcu nie można dojść do wniosku, że „ T ( n ) = O ( n ) ”, ponieważ mówi to coś o funkcji T jako całości i udowodniłeś tylko coś o konkretnej wartości T ( n ) .kN,T(k)ckT(n)=O(n)TT(n)

Musisz wyraźnie powiedzieć, co oznacza Więc może twój dowód brzmi:O

Załóżmy, że dla wszystkich k < n . Następnie T ( n ) = 2 T ( n / 2 ) + n 2 c n / 2 + n ( c + 1 )T(k)ckk<n .T(n)=2T(n/2)+n2cn/2+n(c+1)n

To nie dowodzi kroku indukcyjnego: zacząłeś od , a wykazałeś, że dla k = n , T ( k ) ( c + 1T(k)ckk=n . To jest słabsza granica. Zobacz, co to oznacza: T ( k ) cT(k)(c+1)k oznacza, że C jest związane z szybkością wzrostu T . Ale masz współczynnik c, który rośnie, gdyrośnie k . To nie jest liniowy wzrost!T(k)ckcTck

Jeśli przyjrzysz się uważnie, zauważysz, że współczynnik rośnie o 1 za każdym razem, gdy k podwaja się. Tak więc, nieformalnie, jeśli m = 2 p k, to c m = c k + p ; innymi słowy, c k = c 0 log 2 k .c1km=2pkcm=ck+pck=c0log2k

Można to zrobić precyzyjnie. Udowodnij przez indukcję, że dla , T ( k ) c log 2 ( k ) .k1T(k)clog2(k)

The recurrence relation is typical for divide-and-conquer algorithms that split the data in two equal parts in linear time. Such algorithms operate in Θ(nlog(n)) time (not O(n)).

Aby zobaczyć oczekiwany wynik, możesz sprawdzić relację powtarzalności względem twierdzenia głównego . Podział wynosi a dodatkowa wykonana praca to n ; log 2 ( 2 ) = 1, więc jest to drugi przypadek, dla którego wzrost wynosi Θ ( n2T(n/2)nlog2(2)=1 .Θ(nlog(n))

Gilles „SO- przestań być zły”
źródło
7

I'm extending the answer already given, perhaps only by explaining my comment in more detail.

T(n)=aT(n/b)+f(n)a1 and b>1 are constants and f(n) a function. Note that in our case n/2 can be interpreted to mean n/2n/2

a=2b=2f(n)=Θ(n). This means that we have nlogba=nlog22=n. The second case of the Master theorem applies since f(n)=Θ(n), and we have the solution T(n)=Θ(nlogn).

Juho
źródło
Thanks! It may be noted that "dropping floors and ceils" corresponds to assuming that n=2k which is commonly done. The basic observation is that for non-decreasing functions, the asymptotic growth of subsequences equals the asymptotic growth of the whole sequence.
Raphael