ASD Ćwiczenia 5

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi .

Wskazówka

Zadanie 2

Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań.


Wskazówka

Zadanie 3

Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.


Wskazówka

Zadanie 4

Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze -elementowym wykonuje w pesymistycznym przypadku co najmniej porównań.

Wskazówka

Zadanie 5

Zaproponuj algorytm, który w ciągu długości wyznacza elementy maksymalmy i minimalny wykonując co najwyżej porównania, gdy jest parzyste, a co najwyżej , gdy jest nieparzyste.

Wskazówka