[Algorytmy] Złożoność czasowa algorytmów

[Quaerens]

Niech Alg1, Alg2 i Alg3 będą algorytmami o następującej złożoności czasowej względem danych rozmiaru n:

\(\displaystyle{ T(Alg1,n)=\Theta (nlgn) \\ A(Alg2,n)=\Theta(n), W(Alg2,n)=O(n^2), \\ A(Alg3,n)=\Theta (\sqrt{n}),W(Alg3,n)=\Omega(nlgn)}\)

Określ możliwie dokładnie złożoność czasową następująych algorytmów:

A)

Kod: Zaznacz cały

void Algorytm(int n) {
for(i :=0;i<n;i=i+1)
Alg1(n)
}

B)

Kod: Zaznacz cały

void Algorytm(int n) {
for(i :=0;i<n;i=i+1) {
Alg2(n);
Alg3(n);
}
}

[Crizz]

Mógłbyś wytłumaczyć oznaczenia? Co oznaczają \(\displaystyle{ T,W,A}\)?

[argv]

Obstawiam Average i Worst. T nie wiem.

[Quaerens]

A już zrobiłem. Teraz podpunkt B.

[Crizz]

Rozumiem, że \(\displaystyle{ T}\) to po prostu funkcja kosztu.

No a czym się różni przykład B? Wystarczy logicznie pomyśleć. Mamy \(\displaystyle{ T(Algorytm,n)=\Theta(n) \cdot T(Alg3,n)}\). Któa klasa funkcji dla \(\displaystyle{ A}\) jest większa? Który warunek na \(\displaystyle{ W}\) ma zastosowanie? Zauważ, że nie możemy znaleźć klasy \(\displaystyle{ O}\) dla \(\displaystyle{ W}\), skoro mamy w trzecim algorytmie tylko dolne oszacowanie.

[Quaerens]

No trochę nie rozumie i gubie się, dlaczego akurat dałeś tam Alg3 skoro mamy T(Alg1), wydaje mi się, że winno być to zaznaczone, co kolwiek by to nie znaczyło. Proszę o dalsze wskazówki.

[Crizz]

Hmmm... przepraszam, coś mi się pomyliło. Zamiast \(\displaystyle{ T(Alg3,n)}\) powinno być \(\displaystyle{ T(Alg2,n)+T(Alg3,n)}\) i wyliczając \(\displaystyle{ A}\), bierzesz pod uwagę tę z funkcji \(\displaystyle{ A(Alg2,n),A(Alg3,n)}\), która jest większa.