[Algorytmy]Czas działania algorytmu.

[lisio]

Witam,
bardzo prosiłbym o przedstawienie sposobu rozwiązywania takiego zadania:

Zadanie 21: Nieefektywne sortowanie
Rozważmy następujący algorytm sortowania.

Kod: Zaznacz cały

STOOGE-SORT(A,i,j)
1 if A(i)>A(j)
2    then zmień A(i) z A(j)
3 if i+1 >= j
4    then return
5 k<-[(j-i+1)/3]
6 STOOGE-SORT(A,i,j-k)
7 STOOGE-SORT(A,i+k,j)
8 STOOGE-SORT(A,i,j-k)

Jaki jest czas działania tego algorytmu dla tablicy długości n:STOOGE-SORT(A,1,n)?

[Xitami]

\(\displaystyle{ O\left(n^{log(3)/log(1.5)}\right)}\)

a czy zamiast k<-[(j-i+1)/3]
nie powinno być k<-[(j-i+1)/3+i]

[lisio]

Błąd był zamiast

Kod: Zaznacz cały

3 if i+1 >= j

było

Kod: Zaznacz cały

3 if A(i)+1 >= j

. 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 } ).}\)