Matematické Fórum

Ahoj,

dvojkový logaritmus počtu záznamů, můžeš použít metodu půlení intervalů

Ano, čtení i zápis - u zápisu máš ještě další operaci, a to udělat si "mezeru" v tom souboru, něco samozřejmě stojí fyzické čtení souboru i zápis do něj, ale uvažujme-li "algoritmus který umí najít nějaký záznam v setříděném kontejneru, nebo zapsat záznam do kontejneru bez narušení setříděnosti, tak pak je složitost toho algorimu logaritmická...

A půlení intervalu - funguje to takto (dám triviální příklad)

Mějme setřídené pole o 100 prvcích, ve kterém je uložená posloupnost čísel 0 - 99.

Chceme najít index prvku, ve kterém je uloženo číslo 14, například - tak zpracuješ:

půlka ze 100 je 50. Test, zda hodnota na indexu 50 je rovná, větší, nebo menší než hledaná. V našem případě 49 > 14
Máme jistotu, že v "horní polovině" hledaný prvek nebude
půlka z 50 je 25. Je 14 = 24? není, je 14 > 24 není. Je 14 < 24? Je. Takže použijeme zase levou půlku intervalu

Půlka z 25 je 12 (dělím CELOČÍSELNĚ). Na té je uloženo 13. Testy: 14 = 13? 14 > 13? Je. Použijeme pravou polovinu, interval 13 - 25, tam hledaný prvek bude.
Půlicí bod bude 12+6 (18). Testy, 17 > 13, takže zase levá strana (12 - 17)
Zase půlka, 15.. 16>14 - zase levá strana, (12-15). Zase půlka - 13. 14 = 14 - Nalezeno. Tím jsme zjisitili, že se hledaná hodnota nalézá na indexu [13]. Takhle to vypadá složitě, ale algoritmovat je to strašně jednoduché, přičemž kritéria můžou být jakákoli (samozřejmě, stejně tak kritéria, podle kterého je to pole nebo jiný datový kontejner tříděný.

Tolik ke složitosti hledacího algoritmu, a ty I/O věci bych asi v tomto úkolu neřešil (já bych si nahrál celé pole do paměti, provedl na něm vložení (posun všeho za záznamem, kam má přijít, doprava), soubor bych trunknul a napsal obsah paměti) - za předpokladu, že je to pole dostatečně malé - pro velké objemy dat se nehodí třídění pole, ale spíše zápis "za sebe" s tím, že se to pak setřídí, a nakonec pole není zrovna vhodný typ na setříděná data (velká data). Ale takto bychom mohli filozofovat do noci :)

:) Od začátku jsme se bavili o vyhledávání :) (tedy že chceš přečíst nějaký konkrétní prvek z konkrétního místa (které musíš najít) nebo zapsat na konkrétní místo - tedy které musíš najít :)

Prosté čtení a prostý zápis bez hledání má složitost lineární