Ćwiczenie numer: 5 Data oddania ćwiczenia: Temat: Algorytm dziel i zwyciężaj

1. Treść zadania.

a) Proszę znaleźć najmniejszą odległość pomiędzy dwoma statkami, których pozycje są oznaczone w współrzędnych X i Y (największe prawdopodobieństwo kolizji). Przeszukiwanie należy wykonać dwiema metodami: wyczerpującą i dziel i zwyciężaj. Zależności czasowe dla obu metod przedstawić na wykresie. Należy tak dobrać liczbę węzłów aby możliwe było dokonanie pomiarów.

b) Wnioski ogólne dotyczące efektywności obu metod jaka jest ich złożoność oraz do jakiego typu problemów one należą.

2. Metoda wyczerpująca.

Przykładowy rysunek.

Odległość pomiędzy statkami wyznaczamy ze wzoru:

W metodzie wyczerpującej wyznaczając najmniejsza odległość dokonujemy n*n porównań . Spowodowane jest to tym, że w metodzie tej sprawdzamy odległość pomiędzy wszystkimi statkami (każdy z każdym) i zapisujemy za każdym razem najmniejszą. Złożoność tego algorytmu wynosi O(n²).

3. Metoda dziel i zwyciężaj.

Przykładowy rysunek.

1

3

---