zastanawiałem się jak szybkie jest wyszukiwanie binarne w porównaniu do naiwnego, liniowego przeszukiwania. Wyniki mnie dobiły
Załóżmy, że przeszukujemy żyjącą ludność świata (około 7 i pół miliarda rekordów), chcąc znaleźć daną osobę. Dla zobrazowania przypadku załóżmy, że robimy to "ręcznie" i każda osoba zajmuje nam 1 sekundę.
W przypadku wyszukiwania binarnego, najbardziej pesymistyczny przypadek to 33 sekundy pracy.
W przypadku wyszukiwania liniowego, jest to...
...
Ponad 237 lat.
A teraz przykład z przeszukiwaniem atomów we wszechświecie (tak, wiem - wszyscy to robimy prawie codziennie). Naukowcy szacują, że liczba atomów we wszechświecie to około 1 i 80 zer, czyli:
10000000000000000000000000000000000000000000000000000000000000000000000000000000
0
Metodyka ta sama, szukanie ręczne i jedna sekunda na rekord.
W przypadku wyszukiwania binarnego, najbardziej pesymistyczny przypadek to 266 sekund pracy, czyli niecałe 4 i pół minuty.
W przypadku wyszukiwania liniowego, jest to...
...
Ponad 3168808781402895023702689684893654777296118843004537734174968945673942251 lat.
Zakładając, że wszechświat istnieje od 13,82 miliardów lat, nasz wszechświat musiałby się zacząć i skończyć 229291518191236977113074506866400490397693114544467274542327709 razy, żebyśmy przeszukali liniowo wszystkie atomy naszą metodą.
Bania zryta.
Już mnie tak nie dziwi, że Google jest takie szybkie. Kwestia bardzo dobrego indeksowania, bo samo wyszukiwanie można niesamowicie wręcz przyśpieszyć.
Nerdowa część mnie jest szczęśliwa.
