8719220777

METODY PROBABILISTYCZNE I STATYSTYKA - INFORMACJE UZUPEŁNIAJĄCE

Czas wykonywania obliczeń zależy od danych wejściowych. Przykładowo przy sortowaniu:

•    im krótszy jest ciąg danych tym krótszy jest czas ich posortowania,

•    im bardziej wstępnie posortowany jest ciąg danych tym krótszy jest czas ich całkowitego posortowania.

Jak wiadomo dwoma często stosowanymi sposobami podejścia są: rozpatrywanie przypadków najgorszych (złożoność pesymistyczna) oraz zastosowanie określonego sposobu uśrednienia wszystkich możliwych przypadków (złożoność oczekiwana).

Ocena złożoności obliczeniowej algorytmu może być dokonana teoretycznie lub symulacyjnie -jest ona niezależna od środowiska sprzętowo-programowego. Z kolei ocena złożoności czasowej jest zawsze prowadzona w określonym środowisku sprzętowo-programowym.

Na zakończenie rozważań wstępnych należy podkreślić, że¹ istnieje wiele programów, które testują różne charakterystyki sprzętu komputerowego i oprogramowanie - moc pojedynczej maszyny, interakcje w systemie klient-serwer (z pojedynczym lub wieloma klientami) czy liczbę transakcji na sekundę w systemie przetwarzania transakcyjnego.

W miarę jak pojawiają się nowe wersje oprogramowania i sprzętu, zmieniają się składowe testy benchmarków i ich wagi w obliczaniu wyniku benchmarku - dlatego jednym z warunków uzyskania wiarygodnej oceny w testach porównawczych jest konieczność zastosowania tej samej wersji benchmarku.

1.2. Szacowanie rodzaju / klasy złożoności obliczeniowej danego algorytmu²

W niektórych prostych przypadkach możliwe jest oszacowanie złożoności obliczeniowej bez wykonywania skomplikowanych obliczeń, czy symulacji.

Przykład 1

Wyszukiwanie wartości maksymalnej w ciągu nieposortowanym Załóżmy, że mamy n liczb. Potrzebujemy przejrzeć każdą z nich po to, by określić, która z nich jest największa. Potrzebujemy zatem n operacji ("spojrzeń) - liczba potrzebnych operacji jest proporcjonalna do rozmiaru ciągu - więc złożoność liniowa - O(n).

Przykład 2

Wyszukiwanie danej liczby w ciągu posortowanym.

Pomyślmy jakąś liczbę od 1 do 1000. Można ją zgadnąć zadając maksymalnie 10 pytań na które odpowiada się tak lub nie. A oto pytania:

Czy ta liczba jest mniejsza od 500?

Jeśli tak, to czy jest mniejsza od 250?

Jeśli nie, to czy jest mniejsza od 375?

Jeśli nie, to czy jest mniejsza od 438?

Jeśli nie, to czy jest mniejsza od 469?

Jeśli tak, to czy jest mniejsza od 443?

Jeśli tak, to czy jest mniejsza od 440?

Jeśli tak, to tą liczbą jest 439.

Idea jest taka, że dzięki temu, że ciąg jest posortowany, w kolejnych krokach pomniejszany jest o połowę zakres, w którym znajduje się liczba dzięki temu potrzebne jest ok. Iog2l000 operacji - a więc występuje tu złożoność logarytmiczna - 0(log2n).

4

1

   http://pl.wikipedia.org/wiki/Testowanie wzorcowe

2

   http://forum.ks-ekspert.pI/topic/l 1141 l-algorvtmv-zIozonosc-obliczeniowa/

Data ostatniej aktualizacji: piątek, 29 października 2010