Złożoność czasowa wyszukiwania binarnego dla nieposortowanej tablicy

Question

Utknąłem z dwiema złożonościami czasowymi. Aby wykonać wyszukiwanie binarne z posortowaną tablicą, należy użyć O (logN). Aby przeszukać nieposortowaną tablicę, musimy najpierw ją posortować, aby stała się O (NlogN). Tak więc możemy wykonać wyszukiwanie binarne, które daje złożoność jako O (N), ale przeczytałem, że może to być O (NlogN). Który jest poprawny?

Answer 1

Wyszukiwanie binarne jest dla list "posortowanych". Złożoność to O (logn).

Wyszukiwanie binarne nie działa w przypadku list "nie posortowanych". Dla tych list po prostu wykonaj proste wyszukiwanie zaczynając od pierwszego elementu; daje to złożoność O (n). Jeśli chcesz posortować tablicę za pomocą MergeSort lub dowolnego innego algorytmu O (nlogn), wówczas złożoność będzie miała postać O (nlogn).

O (logn) < O (n) < O (nlogn)

Answer 2

Odpowiedź na Twoje pytanie jest w samym pytaniu. Najpierw sortujesz listę. Jeśli sortujesz listę przy użyciu sortowania szybkiego lub scalania, złożoność staje się o (n log n). Part - 1 kończy się. Druga część wykonywania wyszukiwania binarnego odbywa się na "liście posortowanej". Złożoność wyszukiwania binarnego to o (log n). Dlatego ostatecznie złożoność programu pozostaje o (n log n). Jeśli jednak chcesz obliczyć medianę tablicy, nie musisz sortować listy. Prosta aplikacja liniowego lub sekwencyjnego wyszukiwania może ci w tym pomóc.

Answer 3

Złożoność czasowa wyszukiwania liniowego to O(n), a wyszukiwanie binarne to O(log n) (log base-2). Jeśli mamy nieposortowaną tablicę i chcemy użyć tego wyszukiwania binarnego, musimy najpierw posortować tablicę. I tutaj musimy spędzić czas na uporządkowaniu tablicy, a następnie spędzeniu czasu na szukaniu elementu.