8719220781

Ocena średnia

Przyjmujemy, że z jednakowym prawdopodobieństwem i-ty element jest przemieszczany o możliwą liczbę miejsc: 1 < ti < i. Zatem średnia liczba przesunięć tego elementu jest równa:

i +1

2

_ 1 ^ j. _ 1 i(i +1) _ i k=i i 2

Wówczas funkcja złożoności przedstawia się następująco:

T„(n) = 5n-4+3 £ \ = 5n-4+3 § ^

Suma w powyższej zależności jest równa:

yii + l_lyl. yi 1 _ 1 yl. n~l _ 1 n(n~l) n-l_n-lfn    (n — l)(n — 2)

h 2~    2~~ 2    2    ~2~ ~ ~2~ v2 ~ )    4

Zatem ostatecznie

Czyli podobnie jest przy ocenie pesymistycznej otrzymaliśmy funkcję kwadratową.

Przykład⁶

•    Sortowanie tablicy zawierającej milion liczb (10⁶).

•    Superkomputer: wykonuje 100 milionów (10⁸) operacji na sekundę.

Sortujemy algorytmem przez wstawianie: T(n) = 2n²

T(10⁶) = 2* (10⁶)2 / 10⁸ = 20 000 sekund = 5.56 godzin

•    Komputer osobisty: wykonuje 1 milion (106) operacji na sekundę Sortujemy algorytmem przez scalanie: T(n) = 50nlgn

T(10⁶) = 50 * 10⁶ * lglO⁶ / 10⁶ = 1000 sekund =16.67 minut

•    Komputer osobisty wykonał zadanie 20 razy szybciej.

1.4. Symulacyjna ocena złożoności algorytmów

Analityczna ocena złożoności algorytmów jest możliwa jedynie dla obliczeń stosunkowo prostych. Dla obliczeń skomplikowanych jedyną drogą oceny złożoności jest metoda symulacyjna.

Przy ocenie złożoności obliczeniowej należy opracować model symulacyjny algorytmu, który umożliwia rejestrację liczby wykonywanych operacji elementarnych. Ideę postępowania dla prostego algorytmu przedstawiono na rys. 1.

Dla algorytmu sortowania przez wstawianie kluczowe jest rejestrowanie liczby sprawdzeń warunku pętli for © w i-tym przebiegu. Poniżej zamieszczono wyniki oceny analitycznej i oceny symulacyjnej⁷ dla tego algorytmu.

http://www.sciaga.pl/tekst/45977-46-zlozonosc obliczeniowa algorytmu

Algorytmy sortowania. Opis i demonstracja http://www.home.umk.p1/~abak/wdimat/s/Index.html