przeszukiwanie binarne na listach

0

Jaki jest koszt pesymistyczny mierzony liczbą operacji listowych dla algorytmu wyszukiwania binarnego zaimpelemntowanego na n-elementowej:

a) liście jednokierunkowej;
b) liście dwukierunkowej

Co do samego przeszukiwania to wiem, że stwierdza on w czasie logrytmicznym czy dany element znajduje sie na liscie uorzadkowanej czy tez nie.

0

Wyszukiwanie binarne wymaga dostępu do dowolnego elementu w czasie stałym, czego listy nie udostępniają. Zaimplementowanie wyszukiwania binarnego (praktycznie taki sam algorytm jest do zwracania elementów, jak i do stwierdzania obecności) na tych listach co podałeś da złożoność obliczeniową O(n).

0

Czyli takie samo jak przeszukiwanie liniowe.

0

Wyszukiwanie binarne wymaga dostępu do dowolnego elementu w czasie stałym, czego listy nie udostępniają. Zaimplementowanie wyszukiwania binarnego (praktycznie taki sam algorytm jest do zwracania elementów, jak i do stwierdzania obecności) na tych listach co podałeś da złożoność obliczeniową O(n).

Hmm, na pewno? Nie przemyślałem tego dobrze, ale jak dla mnie wyszukiwanie binarne (a raczej symulowanie wyszukiwania binarnego na listach) ma

Lista jednokierunkowa - O(n ^ 2).
Dlaczego:
Szukanie liczby 8, lista jednokierunkowa:

1 2 3 4 5 6 7 8 9 10 11
przejście do środkowego elementu (6) + przejście do elementu 9 - O(n)
przejście do elementu 8 (albo 7 a następnie 8) - od początku listy... kolejne O(n)

Lista dwukierunkowa - sam nie wiem, strzelałbym O(n log n) (to samo szukanie co poprzednio z tym że każde kolejne szukanie to max log x operacji (x to poprzednia ilość operacji)

edit: rozpędziłem się z tymi obliczeniami, poniższy post zawiera 'poprawki' mojego toku myślenia.

0

Wyszukiwanie binarne wymaga O(lg n) dostępów do danych, więc jeśli pojedynczy dostęp to O(n) to nijak całkowita złożoność nie wyjdzie O(n^2). Złożoność O(n) będzie o ile będziesz pamiętał wskaźniki do końców aktualnie przeszukiwanego przedziału. Wtedy dostęp do środka przedziału ma złożoność O(długość przedziału), a dokładniej długość przedziału / 2, a suma długości wszystkich branych pod uwagę przedziałów jest równa: n + n / 2 + n / 4 + ... + 1 = 2 * n, czyli należy do O(n). Podstawiając jedno do drugiego, ilość operacji na elementach listy wynosi 2 * n / 2 = n.

1 użytkowników online, w tym zalogowanych: 0, gości: 1