ASD k1 11 2005 3

Zadanie 3a W pewnej firmie znajdują się 4 działy, w każdym z nich pracuje m pracowników. Na koniec miesiąca każdy z kierowników działu przesyła do księgowości listę płac w postaci listy par : (Nazwisko, Płaca), gdzie PłacaeR. Listy te są posortowane alfabetycznie niemalejąco według nazwisk (nazwiska mogą się powtarzać, wtedy w obrębie tego samego nazwiska elementy są posortowane rosnąco według wysokości płacy). Dyrekcja co miesiąc oczekuje zaś od księgowości posortowanej według zarobków listy płac dla całej firmy oraz posortowanych według zarobków list płac dla poszczególnych działów (dla osób o tej samej płacy elementy listy powinny być posortowane rosnąco według nazwisk).

Polecenia:

a)    Zaproponuj algorytm, który umożliwi księgowości wykonanie całej pracy w jak najkrótszym czasie.

b)    Oszacuj złożoność zaproponowanego algorytmu.

c)    Oszacuj czas (z rozbiciem na poszczególne etapy) potrzebny na wykonanie całego zadania, jeżeli wiadomo, że można wykonać ok. 1000000 operacji podstawowych (porównania,

przypisania, etc) w ciągu ls.,am< 1000

d)    Czy wiedza z zakresu ASD przydała się w tej sytuacji? Odpowiedź uzasadnij.