Zależność czasowa algorytmu

Odpowiedz Nowy wątek
2012-10-05 18:25
0

Mam podany algorytm.

 for(i=1; 1<n; i++)
for(j=1; j>0 && tab[j]<tab[j-1];j--)
 metoda(a,b);

Następnie muszę wyznaczyć pesymistyczną, optymistyczną oraz średnią złożoność czasową.

Optymistyczna opcja będzie wtedy kiedy druga pętla się nie wykona, czyli złożoność tego będzie wynosiła n ?
Pesymistyczna opcja będzie wtedy kiedy druga pętla wykona się za każdym razem, czyli złożoność tego będzie wynosiła n^2?
Średnia złożoność to (n+n^2)/2 ?

Czy ktoś mi może powiedzieć czy dobrze to rozumiem ?

Pozostało 580 znaków

2012-10-05 18:46
2
  1. Naucz sie formatować kod jak człowiek!
    for(i=1; 1<n; i++)
    for(j=1; j>0 && tab[j]<tab[j-1];j--)
        metoda(a,b);
  2. Zakładamy że jedyna "kosztowna" operacja to rozumiem metoda(a,b) i ma koszt O(1) czy też że porównania (w tym obroty pętli) też są kosztowne?
  3. Optymistycznie złożoność faktycznie będzie O(n) bo wewnętrzna pętla nigdy się nie wykona (to tylko przy założeniu że "pusta" pętla też ma koszt, bo zauważ ze metoda się nijak nie wykonuje!)
  4. Pesymistycznie środkowa pętla będzie się wykonywać, ale wykona się raptem dwa razy (bo po dwóch j-- j będzie już mniejsze od 0), więc mamy O(2*n) = O(n)
  5. Średnio pętla wewnętrzna wykona się raptem raz więc mamy O(n)*O(1) = O(n)

Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2012-10-05 19:10
0

Aj pomyliłem się w kodzie

 for(i=1; 1<n; i++)
     for(j=i; j>0 && tab[j]<tab[j-1];j--)
            metoda(a,b);

W drugiej pętli powinno być j=i a nie j=1.

  1. Faktycznie mało estetycznie, postaram się pamiętać o wcięciach.
  2. W zadaniu nie ma tego sprecyzowanego. Jednak wydaje mi się że chodzi jedynie o pętle (biorąc pod uwagę inne zadania które mam rozwiązane ). Jednak nic nie szkodzi aby rozpatrzyć 2 możliwości.
  3. Czy teraz moja wersja n2 przy poprawionym kodzie jest poprawna ? (patrząc jedynie na pętle). A n2+1 = n^2 licząc razem z metodą?
edytowany 3x, ostatnio: matwiej, 2012-10-05 19:11
n²+1 = n² na pewno nie jest poprawne. ;) a podając złożoność zazwyczaj nie pisze się +1 tylko funkcję najwyższego rzędu bez stałej. n²+1 = O(n²) - dawidgarus 2012-10-06 10:29
O(n²+1) = O(n²) tak to raczej powinno być zapisane. - Azarien 2012-10-15 12:21

Pozostało 580 znaków

2012-10-05 19:24

Teraz tak.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0