Usiłuję zrozumieć, co jest nie tak z następującym dowodem kolejnego wystąpienia
Dokumentacja mówi, że jest błędna z powodu hipotezy indukcyjnej, że
Czego mi brakuje?
Usiłuję zrozumieć, co jest nie tak z następującym dowodem kolejnego wystąpienia
Dokumentacja mówi, że jest błędna z powodu hipotezy indukcyjnej, że
Odpowiedzi:
Powiedzmy, że ostatecznym celem jest udowodnienie, że . Zaczynasz od hipotezy indukcyjnej:T(n)=O(n)
dla wszystkich i < n .T(i)≤ci i<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)n c n T(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)
źródło
Pominąłeś kilka kroków. Wygląda na to, że próbujesz udowodnić przez indukcję, żeT(n)=O(n) , a twój dowód to:
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<n T(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 ) .∀k≥N,T(k)≤ck T(n)=O(n) T T(n)
Musisz wyraźnie powiedzieć, co oznacza Więc może twój dowód brzmi:O
To nie dowodzi kroku indukcyjnego: zacząłeś od , a wykazałeś, że dla k = n , T ( k ) ≤ ( c + 1T(k)≤ck k=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)≤ck c T c k
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 .c 1 k m=2pk cm=ck+p ck=c0log2k
Można to zrobić precyzyjnie. Udowodnij przez indukcję, że dla , T ( k ) ≤ c log 2 ( k ) .k≥1 T(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) n log2(2)=1 .Θ(nlog(n))
źródło
I'm extending the answer already given, perhaps only by explaining my comment in more detail.
źródło