Złożoność czasowa podanego algorytmu

0

Czy ktoś mógłby mi wyjaśnić jaka jest złożoność czasowa tego algorytmu?

for nr1 := 1 to n-1 do
   for nr2  := nr1+1 to n do
      if t[nr1]>t[nr2] then
         begin
            pom := t[nr2];
             t[nr2] := t[nr1];
             t[nr1] := pom
        end
1

Na oko O(n^2).

1

A policz sobie sume takiego ciągu arytmetycznego. Ile razy obraca się pętla? Za pierwszym razem od 2 do n (n-2 razy), za drugim razem od 3 do n (n-3 razy), za i-tym razem od i+1 do n (n-i-1 razy) a za n-1 razem od n do n czyli 1 raz.
Czyli w sumie mamy 1+2+3+4+...+n-i-1+...+n-3+n-2
Czyli ciąg arytmetyczny startujacy z 1, kończący się na n-2 a różnica między wyrazami do 1. Było chyba w szkole jak to policzyć?

0

Kwadratowa, Shalom pokazał jaki to tworzy ciąg. Ogólnie, zawsze gdy jest podwójna pętla i zmienne idą do jakiegoś ułamka n złożoność jest O(n^2).

0

OK, przyznaję się. Próbuję też ogarnąć złożoność, ale nie ogarniam. W jaki sposób to mi się może przydać w praktyce? Tzn. wiem, że np. algorytm O(1) zadziała szybciej niż O(n^2).

5

@Juhas oj niewiele chyba jednak wiesz :P

algorytm O(1) zadziała szybciej niż O(n^2).

Nic bardziej mylnego, jedno z drugim niewiele ma wspólnego. Rząd złożoności obliczeniowej mówi o tym jak wzrasta czas wykonania algorytmu w zależności od rozmiaru danych wejściowych. Algorytm O(1) działa zawsze tak samo długo. Dla algorytmu O(n) czas rośnie liniowo, więc jeśli np. rozmiar danych zwiększysz 10 razy to czas wykonania wzrośnie ~10 razy. Dla algorytmu O(n^2) czas rośnie kwadratowo, wiec dla 10 razy większych danych algorytm będzie działa już 100 razy dłużej. To oznacza że asymptotycznie dla n -> nieskończoności algorytm O(1) będzie wolniejszy od O(n^2), ale wcale nie oznacza to że dla wszystkich praktycznych danych taka zależność zachodzi.

Załózmy że masz algorytm wyszukiwania ścieżki w grafie, uzyty np. w nawigacji samochodowej do wytyczania trasy. Jeśli robisz to algorytmem o złożonosci O(1) to niezależnie od tego skąd i dokąd chcesz jechać trasa wyliczy sie w tym samym czasie. Ale jeśli algorytm działa w czasie O(n^3) to czas wytyczania trasy 100 km będzie 1000 razy dłuższy od wytyczania trasy 10 km! Jeśli teraz 10 km obliczało się 1s to na 100km będzie trzeba poczekać prawie 20 minut...

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