Zadanie informatyka pomocy

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij Thank icon

Zadanie informatyka pomocy

Postprzez polaxcx » 10 Kwi 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
polaxcx
Rozkręcam się
Rozkręcam się
 
Posty: 29
Dołączenie: 03 Sty 2019, 17:16
Płeć: On
Otrzymane podziękowania: 0

Postprzez HubaBuba » 14 Maj 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
HubaBuba
Witam na forum
Witam na forum
 
Posty: 4
Dołączenie: 05 Mar 2019, 22:14
Otrzymane podziękowania: 0


Powróć do Pomocy! - informatyka



Kto jest na forum

Użytkownicy przeglądający to forum: CommonCrawl [Bot] oraz 0 gości