Vyhladavanie v utriedenom poli

Sekcia: Programovanie 05.03.2009 | 08:32
Avatar Pali   Používateľ
Cawte,
na hladanie v utriedenom zozname pouzivame binary search s casovou
zlozitostou log(n). Ale ak mam zoznam s utriedenimi prvkami, pricom
pre i-ty prvok plati, ze rozdiel medzi prvkami i a i-1 je mensi ako
medzi i-1 a i-2, da sa to nejak rychlejsie ako log(n)?
    • Re: Vyhladavanie v utriedenom poli 06.03.2009 | 00:32
      stando   Návštevník
      asymptoticky to nezlepsis. A ak jedina vlastnost je, ze "medzeri" medzi cislami sa stale zmensuju tak z toho tiez vela neuvaris :)
      • Re: Vyhladavanie v utriedenom poli 06.03.2009 | 20:57
        Avatar Pali   Používateľ
        Ak vsak potrebujeme hladat viac ako n cisel v tomto poli, neda sa jedno hladanie zlepsit?
        Ak tych cisel hladame viac, vieme si spocitat sucet medzier. No ak sa tie medzery medzi cislami zmensuju, tak vieme, ze predposledna medzera je minimalne rovna poslednej a taktiez potom vieme aky je sucet medzier od prvej po predposlednu (ak si ich na zaciatku scitame). Neda sa nejak takto skakat od poslednej hodnoty pola az k hladanej (ak existuje) na menej nez log(n) krokov (napr log(log(n)) alebo log*(n))?
        • Re: Vyhladavanie v utriedenom poli 07.03.2009 | 13:39
          stando   Návštevník
          no ak hladas viac cisel tak by si mozno mohol vyuzit posledne najdene a hladat iba v jednej "polovici" pola. teda od prveho cisla do najdeneho, alebo od najdeneho do posledneho.

          ak hladas viac cisel, mozno by stalo za uvahu ich zotriedit a vyhladavat tiez delenim intervalov...myslim, ze mas cisla 1, 5, 8, 12, 24 a ty chces vyhladat 8. A ak sa dostanes do situacie, ze vsetky cisla su vacsie ako 8, tak 1 a 5 uz nemusis hladat.