length; i++) e
if (search(ye x[i]) != -1)
D:\Skład\Struktury danych i techniki obiektowe na przykładzie Javy 5.0\kalki\r02-11.doc (01-03-06) — 139 —
140
Rozdział 2. ¨ Poprawność i wydajność programów
return false;
}
return true;
}
Ciało pętli zostanie wykonane x.length razy. Niestety, pętla korzysta z metody search(), która zawiera pętlę wykonywaną y.length razy dla każdego wywołania metody. W ten sposób łączny czas wykonania jest proporcjonalny do iloczynu x.length i y.length.
Przykład 2.17
Rozważmy problem sprawdzenia, czy każdy element tablicy jest unikatowy. Zadanie to wykonuje poniższa metoda:
/** Sprawdza, czy wszystkie wartości tablicy są unikatowe.
@param x Sprawdzana tablica.
@return Wartość true, jeśli wszystkie elementy tablicy są unikatowe.
*/
public static boolean areUnique(int[] x) e
for (int i = 0; i < x.length; i++) e
for (int = 0; < x.length; ++) e
if (i != && x[i] == x[ ])
return false;
}
}
return true;
}
Jeśli wszystkie wartości są unikatowe, zewnętrzna pętla for wykona się x.length razy.
Wewnętrzna pętla dla takiego przypadku również wykona się x.length razy. Oznacza to, iż ciało wewnętrznej pętli wykona się łącznie (x.length)2 razy.
Przykład 2.18
Metoda przedstawiona w przykładzie 2.17 jest mało wydajna. Wykonuje dwa razy wię-
cej sprawdzeń niż jest to konieczne. Można ją zmodyfikować w następujący sposób:
/** Sprawdza, czy wszystkie wartości tablicy są unikatowe.
@param x Sprawdzana tablica.
@return Wartość true, jeśli wszystkie elementy tablicy są unikatowe.
*/
public static boolean areUnique(int[] x) e
for (int i = 0; i < x.length; i++) e
for (int = i + i; < x.length; ++) e
if (x[i] == x[ ])
return false;
}
}
return true;
}
— 140 — (01-03-06)
D:\Skład\Struktury danych i techniki obiektowe na przykładzie Javy 5.0\kalki\r02-11.doc
2.8. Wydajność algorytmów
141
Za pierwszym razem wewnętrzna pętla wykona x.length-t iteracji. Za drugim razem wewnętrzna pętla wykona x.length-2 iteracji itd. Za ostatnim razem wykona tylko jedną iterację. Łączna liczba wykonań będzie więc równa:
x.length-1 + x.length-2 + ... + 2 + 1
Ciąg 1+2+3+…+(n–1) jest bardzo dobrze znanym ciągiem, którego wartość wynosi ( - )
1
ń
n
2
co daje x.length×(x.length–1)/2 lub 0,5×(x.length)2–0,5×x.length.
Notacja dużego O
Ten rodzaj analizy jest obecnie ważniejszy w trakcie prac nad wydajnym oprogramo-waniem niż mierzenie czasu wykonania programu w milisekundach na konkretnym komputerze. Zrozumienie, w jaki sposób czas wykonania (i wymagania pamięciowe) rośnie jako funkcja zwiększającej się liczby danych wejściowych, pozwala porównywać różne algorytmy. Naukowcy opracowali użyteczną terminologię i notację ułatwiającą opisywanie związku między liczbą elementów wejściowych a czasem wykonania. Jeśli na przykład czas wykonania zwiększa się dwukrotnie w momencie dwukrotnego zwiększenia liczby danych, oznacza to, iż algorytm ma liniową złożoność obliczeniową. Mówi się wtedy, iż złożoność obliczeniowa jest rzędu n. Jeśli natomiast czas działania zwiększa się czterokrotnie po dwukrotnym zwiększeniu liczby elementów, oznacza to algorytm o kwadratowej złożoności obliczeniowej. Mówi się wtedy, iż złożoność obliczeniowa jest rzędu n2.
Przedstawiliśmy wcześniej cztery metody: w jednej z nich czas wykonania był zwią-
zany z x.length, w innej był związany z x.length razy y.length, w jeszcze innej był
związany z (x.length)2, a w ostatniej był związany z (x.length)2 i x.length. Informatycy używają notacji O(n) do oznaczenia pierwszego przypadku, O(n×m) do oznaczenia drugiego przypadku, O(n2) do oznaczenia trzeciego i czwartego przypadku. Element n to x.length, a element m to y.length. Symbol O (pisany w wielu książkach z zastosowaniem różnych stylów) warto rozumieć jako „rząd wielkości”. Tego rodzaju notacja nosi nazwę notacji dużego O (ang. big O notation).
W trosce o komfort korzystania z naszego serwisu chcemy dostarczać Ci coraz lepsze usługi. By móc to robić prosimy, abyś wyraził zgodę na dopasowanie treści marketingowych do Twoich zachowań w serwisie. Zgoda ta pozwoli nam częściowo finansować rozwój świadczonych usług.
Pamiętaj, że dbamy o Twoją prywatność. Nie zwiększamy zakresu naszych uprawnień bez Twojej zgody. Zadbamy również o bezpieczeństwo Twoich danych. Wyrażoną zgodę możesz cofnąć w każdej chwili.