Rozwiązywanie równania rekurencyjnego $T(n)=T(k)+T(n-k-1)+O(n)$
Pytanie jest jasne w tytule. Próbuję rozwiązać tę rekursję, aby pokazać, że najgorszy przypadek algorytmu szybkiego sortowania występuje, gdy$k=0$, ale nie mogę tego zrobić. Mógłbym zrobić następujące konkretne przypadki (używając wielokrotnie tej samej rekursji):
1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$
Czy ktoś może mi pomóc rozwiązać tę ogólną sprawę (lub przynajmniej zasugerować inny sposób, aby udowodnić, że jest najgorszy) $k=0$)?
PS Nie znam twierdzenia Mistrza, więc byłbym wdzięczny za rozwiązanie bez jego użycia (o ile ma to tutaj zastosowanie).
Odpowiedzi
Rozważ nawrót $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$co jest jedną z formalizacji najgorszego przypadku czasu działania funkcji quicksort. Pokażmy przez indukcję, że maksimum osiąga się przy$k = 0$ (lub $k = n$). Pokażemy to, jednocześnie pokazując to$T(n) = \frac{n(n+1)}{2}$.
Podstawa, $n=0$, jest jasne. A teraz przypuśćmy, że$T(m) = \frac{m(m+1)}{2}$ dla wszystkich $m \leq n$i rozważ $T(n+1)$. Funkcja$T(k)$ jest wypukły na interwale $[0,n]$ (rozszerzamy ją na wartości rzeczywiste za pomocą tej samej formuły), a więc maksimum $T(k) + T(n-k)$ jest osiągany w $k=0$ (lub $k=n$). W związku z tym$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$
Zamiast argumentować za pomocą wypukłości, możemy również argumentować bezpośrednio: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ która jest wyraźnie zmaksymalizowana (wyjątkowo) kiedy $k = 0$ lub $k = n$.