przeszukiwanie binarne na listach

Odpowiedz Nowy wątek
2011-09-03 16:05
józef92
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.

Takich zadań też nie robiliscie? Szkoda słów... - Shalom 2011-09-03 21:00

Pozostało 580 znaków

2011-09-03 17:12
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).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-03 17:14
józe92
0

Czyli takie samo jak przeszukiwanie liniowe.

pesymistycznie szukasz ostatniego elementu wiec będziesz musiał przejść całą listę ;) - Shalom 2011-09-03 17:22
Nie w przypadku dwukierunkowej. Tam pesymistyczny jest środek. - Wibowit 2011-09-03 19:39

Pozostało 580 znaków

2011-09-03 19:29
msm
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.

edytowany 6x, ostatnio: msm, 2011-09-03 20:04

Pozostało 580 znaków

2011-09-03 19:43
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Zakładając taką właśnie implementację. W naiwnej wersji będzie to O(n lg n). Póki co, wróżymy z fusów ;) - ElevenEleven 2011-09-06 00:32

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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