Strona 1 z 1
[Algorytmy] Złożoność czasowa algorytmów
: 31 sie 2011, o 13:07
autor: 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);
}
}
[Algorytmy] Złożoność czasowa algorytmów
: 31 sie 2011, o 15:38
autor: Crizz
Mógłbyś wytłumaczyć oznaczenia? Co oznaczają \(\displaystyle{ T,W,A}\)?
[Algorytmy] Złożoność czasowa algorytmów
: 31 sie 2011, o 15:41
autor: argv
Obstawiam Average i Worst. T nie wiem.
[Algorytmy] Złożoność czasowa algorytmów
: 31 sie 2011, o 15:59
autor: Quaerens
A już zrobiłem. Teraz podpunkt B.
[Algorytmy] Złożoność czasowa algorytmów
: 31 sie 2011, o 16:15
autor: 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.
[Algorytmy] Złożoność czasowa algorytmów
: 6 wrz 2011, o 18:30
autor: 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.
[Algorytmy] Złożoność czasowa algorytmów
: 8 wrz 2011, o 12:41
autor: 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.