Zadanie informatyka pomocy

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

Zadanie informatyka pomocy

Post autor: polaxcx »

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, 21:14
Otrzymane podziękowania: 1 raz

Post autor: HubaBuba »

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
Damian1983
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 12 gru 2019, 11:51
Podziękowania: 1 raz
Płeć:

Re: Zadanie informatyka pomocy

Post autor: Damian1983 »

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