Zadanie informatyka pomocy

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
polaxcx
Dopiero zaczynam
Dopiero zaczynam
Posty: 29
Rejestracja: 03 sty 2019, 17:16
Płeć:

Zadanie informatyka pomocy

Post autor: polaxcx » 10 kwie 2019, 00:05

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

HubaBuba
Witam na forum
Witam na forum
Posty: 4
Rejestracja: 05 mar 2019, 22:14

Post autor: HubaBuba » 14 maja 2019, 19:06

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