Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Szukanie w tablicach (binarne czy liniowe)?

greep 05 Kwi 2010 17:43 1004 1
  • #1 05 Kwi 2010 17:43
    greep
    Poziom 19  

    Zastanawiam sie co bedzie lepszym rozwiazaniem (co bedzie mialo mniejsza zlozonosc algorytmu):

    1) Szukanie liniowe w tablicy
    Wedlug notacji duze O, szukanie liniowe ma zlozonsc O(n).


    2) Sortowanie tablicy i szukanie binarne?
    Wedlug notacji duze O, szukanie binarne ma zloznonosc O(Log n), czyli jest szybsze od liniowego ale ale do tego jeszcze dochodzi sortowanie tablicy, co ma srednia zlozonosc O(n Log n) - to jest dla sortowania metoda QuickSort (uzywanego przez JAVA: Arrays.sort()) )
    Czyli ogolem do posortowania i przeszukania tablicy musimy zuzyc: O(Log n) * O(n Log n).

    Czy mam racje?
    Czy zawsze jesli mamy do czynienia z nieposortowana tablica (array), najlepsza metoda jest przeszukiwanie tablicy metoda liniowa (linear)?

    z gory dzieki za info

    0 1
  • Pomocny post
    #2 05 Kwi 2010 18:07
    Dżyszla
    Poziom 42  

    Suma złożoności, nie iloczyn! Najpierw sortujesz, potem szukasz. Więc do złożoności sortowania doklejasz złożoność wyszukiwania. Iloczyn byłby wtedy, gdyby przed każdym podziałem trzeba było dokonać sortowania, a ono jest tylko raz.

    Metoda liniowa nie jest najlepszą. Jest po prostu jedyną metodą przeszukiwania nieposortowanych danych ;)

    0