Błąd w użyciu notacji asymptotycznej

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

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

dla wszystkich i < n .$T(i) \leq ci$$i < n$

Aby ukończyć dowód, musisz również wykazać, że również.$T(n) \leq 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) \leq (c+1)n$$c$$n$$T(n) = \mathcal{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)$$\Theta(n \log n)$

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 ) ≤ $T(k) = O(k)$$k<n$ dla niektórych c . Następnie T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + $T(k) \le c \, k$$c$ , więc T ( n ) = O ( n ) .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$$T(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 ) ≤ $T(k) = O(k)$$k \lt 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 ) .$\forall k \ge N, T(k) \le c \, k$$T(n)=O(n)$$T$$T(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) \le c \, k$$k < n$ .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$

To nie dowodzi kroku indukcyjnego: zacząłeś od , a wykazałeś, że dla k = n , T ( k ) ≤ ( c + $T(k) \le c \, k$$k=n$ . To jest słabsza granica. Zobacz, co to oznacza: T ( k ) ≤ $T(k) \le (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) \le c \, k$$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=2^p k$$c_m = c_k + p$$c_k = c_0 \log_{2} k$

Można to zrobić precyzyjnie. Udowodnij przez indukcję, że dla , T ( k ) ≤ c log 2 ( k ) .$k \ge 1$$T(k) \le c \log_2(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 $\Theta(n\,\mathrm{log}(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 Θ ( $2T(n/2)$$n$$\log_2(2) = 1$ .$\Theta(n\,\log(n))$

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

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

$a = 2$$b = 2$$f(n) = \Theta(n)$. This means that we have $n^{\log_b a} = n^{\log_2 2} = n$. The second case of the Master theorem applies since $f(n) = \Theta (n)$, and we have the solution $T(n) = \Theta (n \log n)$.