Namų darbas
Ką atiduoti
algo su count ir radix, praeinantį go test ./..., ir ataskaitą.
1. Trys rikiavimai, vienas raktas
n = 1 000 / 10 000 / 100 000, raktas Rating:
| n | skaičiavimo | sort.SliceStable |
santykis |
|---|
Kaip santykis kinta didėjant n? Paaiškink, remdamasis O(n + k) ir O(n log n).
2. Riba, ties kuria k nugali
Rask mažiausią k, kuriam skaičiavimo rikiavimas tampa lėtesnis už
sort.SliceStable prie n = 10 000.
Didink dirbtinį rakto intervalą ir matuok. Nurodyk k ir k/n santykį.
3. Trys stabilumo pakopos
Vienu sakiniu kiekvienai:
- 7 pamoka: kas nutinka su nestabiliu rikiavimu?
- 8 pamoka: kas nutinka?
- 9 pamoka: kas nutinka?
Tada vienu sakiniu — kodėl tai ta pati savybė, o pasekmės tokios skirtingos.
4. Kada raktas verčiamas
Skaičiavimo rikiavimui reikia sveikojo skaičiaus iš žinomo intervalo.
Nurodyk du savo bibliotekos duomenų atvejus, kurių raktas iš pirmo žvilgsnio netinka, bet gali būti paverstas tinkamu. Vienam iš jų realizuok ir pamatuok.
(Užuomina: pirmoji raidė. Dešimtmetis. Įvertinimas, suapvalintas iki penkių.)
5. Sprendimas
Vienas pastraipos atsakymas: tavo bibliotekos rikiavimams — kur naudosi skaičiavimo rikiavimą, o kur palyginimų?
Nurodyk kiekvieną Item lauką ir sprendimą kiekvienam. Ten, kur atsakymas
„palyginimų", pasakyk kodėl — ir jei priežastis ta pati kaip trims kitiems
laukams, pasakyk ir tai.