Namų darbas

Ką atiduoti

algo su sort komanda, praeinantį go test ./..., ir matavimų ataskaitą.

1. Kvadratinė kreivė

Pamatuok visus tris algoritmus, n = 1 000 / 10 000 / 50 000, -order shuffled:

n	algoritmas	palyginimai	sukeitimai	laikas

Įrodyk, kad palyginimų skaičius auga ×100, kai n auga ×10. Ar tavo laikas auga taip pat? Jei ne — paaiškink, remdamasis 5 žingsniu.

(Šimto tūkstančių burbuliukų rikiavimo paleisti nebūtina — pamokoje tai užtruko pusantros minutės. Jei paleisi, užrašyk laiką.)

2. Keturios tvarkos

Vienas algoritmas — įterpimo — keturios tvarkos, n = 10 000:

tvarka	palyginimai	sukeitimai	laikas
sorted
nearly
shuffled
reverse

Nurodyk santykį tarp geriausio ir blogiausio atvejo.

3. Sukeitimai prieš palyginimus

Išrinkimo rikiavimas atlieka daugiau palyginimų už burbuliukų ir vis tiek greitesnis.

Pamatuok abu ir apskaičiuok, kiek kartų vienas sukeitimas brangesnis už vieną palyginimą tavo mašinoje. Nurodyk skaičių ir kaip jį gavai.

4. Rikiavimo atsipirkimas

6 pamokos namų darbe skaičiavai, kiek dvejetainių paieškų atperka vieną sort.Slice.

Pakartok su savo rikiavimu. Kiek paieškų atperka vieną InsertionSort 100 000 įrašų? Ar atsakymas apskritai turi prasmę?

5. Sprendimas

Vienas pastraipos atsakymas: tavo bibliotekoje įrašai pridedami po vieną ir retkarčiais prireikia surikiuoto sąrašo.

Ką darysi? Rikiuosi kaskart? Laikysi nuolat surikiuotą? Rikiuosi tik prieš paiešką? Pagrįsk skaičiais iš 1 ir 2 punktų, ir pasakyk, kuris iš trijų algoritmų čia tinkamiausias — jei apskritai kuris nors.