Błąd był zamiast
było
. Jednak ciągle nie wiem jak obliczyć tutaj czas działania algorytmu.
Zadanie rozwiązane : Dla ciekawych jak:
Dowód przez indukcję .
n = 1: Łatwo zauważyć, że STOOGE-SORT poprawnie sortuje
tablicę z tylko jednym elementem.
Indukcyjny: Załóżmy, że STOOGE -SORT poprawnie sortuje tablicę A [1. . . n].
Musimy korzystać z tego założenia, aby udowodnić, że STOOGE -SORT poprawnie
sortuje tablicę A [1. . . n + 1] Załóżmy, że sortujemy tablicę STOOGE -SORT (A,
1, n +1). Następnie z założenia indukcyjnego wiemy, że linia 6 poprawnie
sortuje pierwsze dwie trzecie tablicy (2/3)*(n+1). Także przez indukcyjne hipotezy,
wiemy, że linia 7 poprawnie sortuje ostatnie dwie trzecie tablicy . Tutaj
indukcja nadal obowiązuje, ponieważ ostatnie dwie trzecie tablicy
ma co najwyżej n elementów. Ponadto, wszystkie elementy w ciągu ostatnich dwóch trzecich
tablicy są sortowane i jest ich co najmniej tak dużo, jak wszystkich elementów
w pierwszej tercji. Wreszcie, linia 8 poprawnie
sortuje pierwsze dwie trzecie tablicy i wynika, że A [1. . . n + 1]
jest prawidłowo posortowane.
T(n) = 3T(2n/3) + O(1).
T(n) =
\(\displaystyle{ \theta(n^{log _{3/2}3})}\)
Z Master theorem – część 1
Twierdzenie(Master Theorem): Załóżmy, ze a,b są liczbami dodatnimi oraz c dodatnia liczba naturalna a T jest funkcja, która dla potęg liczby c spełnia równanie:
T(n)=
\(\displaystyle{ \begin{cases} b\hspace{2mm} dla\hspace{2mm} n=1 \\ aT(n/c)+b*n \hspace{2mm} dla \hspace{2mm} n>1 \end{cases}}\)
Wtedy dla liczb naturalnych n będących potęgami liczby c mamy:
1. jeżeli a < c to T = O(n),
2. jeżeli a = c to T = O(n log(n)),
3. jeżeli a > c to T = O
\(\displaystyle{ (n ^{log _{c}a } ).}\)