Witam.
Czy ktoś mógłby mi obajśnić następujące zadania:
Zad. 1
Zaproponuj algorytm typu „dziel i zwyciężaj” do znalezienia elementu największego w
danym ciągu n elementowym zapisanym w tablicy T.
● Opisz słowami ideę algorytmu,
● Zapisz algorytm w pseudokodzie.
● Oszacuj jego koszt.
Zad. 2
W pewnej prezentacji działania algorytmu SelectionSort (sortowanie w porządku rosnącym)
liczby zostały przedstawione jako słupki o wysokości proporcjonalnej do wartości liczby. W
każdym kroku algorytmu porównywane liczby są wyświetlane innym kolorem przez 300 ms,
tak by sposób sortowania był wyraźnie widoczny dla obserwatora.
● Ile co najmniej czasu zajmie oglądanie tej animacji, jeśli ciąg danych zawiera 100
losowo wybranych liczb.
● Ile czasu zajmie oglądanie animacji, jeśli wiemy, że dany 100 elementowy ciąg liczb
jest uporządkowany rosnąco.
Najlepiej, jakby ktoś rozwiązał podane zadania z objaśnieniem, bo podobnych zadań mam około 15 i chciałbym na podstawie rozwiązania tych robić kolejne
Z góry dziękuję za wszelkie odpowiedzi
Algorytm "dziel i zwyciężaj" oraz "SelectionSort"
-
- Użytkownik
- Posty: 941
- Rejestracja: 17 gru 2007, o 21:48
- Płeć: Mężczyzna
- Lokalizacja: Kingdom Hearts
- Podziękował: 6 razy
- Pomógł: 222 razy
Algorytm "dziel i zwyciężaj" oraz "SelectionSort"
co do 2)
Selection Sort jest specyficznym algorytmem, który wykonuje stałą liczbę operacji w zależności od ilości danych do posortowania, niezależną od sposobu ułożenia (np jak w insertion sorcie).
Ilość porównań wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\)
gdzie u nas \(\displaystyle{ n=100}\)
Zatem odp do a i b wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\) pomnożone przez 300 ms (zakładam, że elementy zamieniane nie są porównywane, czyli program nie zatrzymuje się na 300 ms przed zamianą elementów)
Selection Sort jest specyficznym algorytmem, który wykonuje stałą liczbę operacji w zależności od ilości danych do posortowania, niezależną od sposobu ułożenia (np jak w insertion sorcie).
Ilość porównań wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\)
gdzie u nas \(\displaystyle{ n=100}\)
Zatem odp do a i b wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\) pomnożone przez 300 ms (zakładam, że elementy zamieniane nie są porównywane, czyli program nie zatrzymuje się na 300 ms przed zamianą elementów)