binsearch z "wyłączaniem" niektórych elementów

0

Witam!

Szukam modyfikacji do binsearcha, która pozwoliłaby mi "wyłączać" niektóre elementy ciągu tak aby binsearch ich nie dotyczył. Powiedzmy, że mam jakąś posortowaną macierz o N elementach. Potrafię w czasie stałym powiedzieć, czy dany element jest "wyłączony" , czy nie. Chciałbym teraz wyszukać w tej tablicy za pomocą binsearcha element spełniający jakieś moje kryteria nie uwzględniając przy tym "wyłączonych" elementów. Takich operacji chciałbym móc wykonać dowolnie dużo i za każdym razem chcę móc wyłączać dowolne elementy ciągu. Oczywiście nie mogę sobie tak po prostu za każdym razem usuwać tych elementów bo trwałoby to liniowo długo, a to musi koniecznie działać w n log n . Czy to w ogóle jest możliwe?

0

Co to znaczy "nie uwzględniając tym wyłączonych elementów"? Jak funkcja znajdzie jeden z nich, to ma zwrócić, że nie znaleziono?

0

tak

0

O(nlogn) nie będzie, bo macierz jest n * n. Teraz, skąd binary search ma wiedzieć, których elementów nie zwracać? Nie prościej, nieszukać wyłączonych elementów, skoro Wiesz jakie to są?

0

Jeśli wyłączanie polega na tym, że dopiero podczas porównywania elementu (w sensie: sprawdzania warunku wyszukiwania na wytypowanym elemencie) dowiadujemy się, że jest wyłączony no to sorry - pesymistyczny czas wyszukiwania będzie liniowy, bo w pesymistycznym przypadku wszystkie elementy są wyłączone i trzeba sprawdzać wszystkie elementy, by się o tym przekonać. W takim przypadku po prostu najpierw zrób binsearcha tak, jakby wszystkie elementy były włączone, a potem (jeśli początkowo trafiłeś na wyłączony element) liniowo skanuj w odpowiednim kierunku, aż znajdziesz włączony element.

Natomiast jeśli wyłączanie jest osobnym krokiem od szukania to po prostu użyj posortowanego zbioru (lub dwóch - jeden z włączonymi elementami, a drugi z wyłączonymi). Posortowane zbiory są zwykle oparte o zrównoważone drzewa poszukiwań binarnych, gdzie wyszukiwanie, dodawanie i usuwanie elementów zajmują czasy logarytmiczne.

0

Może kopiuj elementy nie wyłączone do nowej struktury, w której zrobisz binarysearch, Jeśli x to procent nie wyłączonych elementów to wtedy złożoność wszystkich operacji wynosi N + Nxlog(N*x). Już przy x=94% liczba operacji jest zbliżona do czasu na wszystkich N elementach, Jeśli ten procent wyłączonych jest mniejszych niż 6% to myślę, że szkoda zachodu.

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