eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingWyszukiwanieWyszukiwanie
  • X-Received: by 10.182.117.40 with SMTP id kb8mr231448obb.7.1461876062358; Thu, 28 Apr
    2016 13:41:02 -0700 (PDT)
    X-Received: by 10.182.117.40 with SMTP id kb8mr231448obb.7.1461876062358; Thu, 28 Apr
    2016 13:41:02 -0700 (PDT)
    Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!goblin3!goblin1!goblin.stu.neva.ru!sq19no2132270igc.0!news-out.google.
    com!uv8ni218igb.0!nntp.google.com!i5no784232ige.0!postnews.google.com!glegroups
    g2000goo.googlegroups.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Thu, 28 Apr 2016 13:41:01 -0700 (PDT)
    Complaints-To: g...@g...com
    Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.37.232.66;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    NNTP-Posting-Host: 178.37.232.66
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <6...@g...com>
    Subject: Wyszukiwanie
    From: "M.M." <m...@g...com>
    Injection-Date: Thu, 28 Apr 2016 20:41:02 +0000
    Content-Type: text/plain; charset=ISO-8859-2
    Content-Transfer-Encoding: quoted-printable
    Xref: news-archive.icm.edu.pl pl.comp.programming:209347
    [ ukryj 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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: