forum.zadania.info

W pewnym pliku znajduje się k rekordów uporządkowanych
leksykograficznie. Przyjmijmy, że identyfikacja jednego rekordu
zajmuje 1sek.
• le co najwyżej czasu potrzeba do odnalezienia poszukiwanego
rekordu, jeśli k=4096 i przeglądamy plik sekwencyjnie ?
• Ile co najwyżej potrzeba czasu , jeśli zastosujemy algorytm
poszukiwań binarnych i k=4096?.
• Jeśli k=1024 i zużyliśmy 12 sek. do znalezienia właściwego rekordu,
to jaki algorytm był zastosowany: sekwencyjny czy binarnych
poszukiwań ?

Bardzo prosze o wytłumaczenie

1. Powiedzmy że nasz rekord znajduje sie na samym końcu pliku. Na początek przeglądamy rekord nr.1 w 1 sek, rekord nr.2 w 1 sek... i takaż dojdziemy do rekordu nr 4096, który jest przez nas poszukiwaniy. Po drodze odwiedziliśmy w kolejności alfabetycznej wszystkie rekordy, co zajęło nam 4096s.
2. W tym przypadku długość przeszukiwanego przedziału w każdym kroku zmniejsza się o połowę. Na początku wynosi ona 4096/2, potem 4096/2/2, potem 4096/2/2/2 i tak w i tym kroku nasz przedział ma 4096/2^i rekordów. Wykonujemy kolejne kroki aż 4096/2^s=1
Stąd s = log2 (4096), czyli s = 12
3. Zauważmy że urzywając poszukiwania binarnego wykonamy maks m operacji, gdzie 1024/2^m=1. Czyli m = 10.
Skoro przesukiwanie zajęło nam więcej niż 10sek to musieliśmy przeczukiwać plik sekwencyjnie

Huba buba, heh, kiedyś taka guma balonowa była