-
Data: 2016-04-28 22:41:01
Temat: Wyszukiwanie
Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]
Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
tylko do określonego przypadku. Metoda pełnego przeglądu jest
bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
dla ogromnych ciągów dających się dobrze aproksymować jakąś
wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
metoda, nawet pesymistycznie działa w czasie LogN, jednak
ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
narzut.
Jak powinno wyglądać adaptatywne wyszukiwanie?
Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
zapamiętujemy przybliżony czas. Potem szukamy metodą
pełnego przeglądu, jeśli czas jest większy, to
przerywamy i wyszukujemy binarnie. Potem z... nie
wiem ile... z 20 razy wyszukujemy binarnie, bo
działało najszybciej. Potem znowu jakaś próba... może z
wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
dane po każdym wyszukiwaniu mogą się zmienić co do
ilości i jakości.
Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
większa niż N to binarnie, a poza tym pełen przegląd?
Druga sprawa, czy interpoluje się tylko liniowo, czy
warto próbować jeszcze jakąś inną funkcją?
Pozdrawiam
Następne wpisy z tego wątku
- 30.04.16 23:23 Wojciech Muła
- 02.05.16 08:07 M.M.
- 06.05.16 12:12 Wojciech Muła
- 07.05.16 08:48 M.M.
- 07.05.16 16:10 M.M.
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-20 Fiat 125p wer. pikup - w PRL moszna było, w III Reczy [pospolitej] nie moszna
- 2024-05-19 Pożar salonu z chińskimi elektrykami
- 2024-05-18 LED
- 2024-05-19 ceny nieruchomości
- 2024-05-18 Szczecin => UX/UI Designer <=
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=