Maksymalna wartość w przedziale

0

Cześć!

W jaki sposób można najlepiej w czasie logarytmicznym obliczyć maksymalną wartość w danym przedziale tablicy? Próbowałem za pomocą drzewa BST, sprawdzając poprzednie klucze od minimalnej wartości do maksymalnej dopóki prawy klucz jest różny od NULL. Jednak poprzednik może być wartością spoza przedziału, więc algorytm jest niepoprawny. Nie mam już żadnych pomysłów.

Z góry dziękuję za pomoc.

0

Chcesz w czasie O(logn) wybrać maksimum z nieposortowanej tablicy? Jak ci się uda to zgłoś się po nagrodę Turinga ;]

0

Dzięki, nie marzyłem o niczym innym, niż o tak szczegółowej odpowiedzi. Gratuluję wysiłku włożonego w napisanie tego posta.

Uczęszczam na kółko informatyczne i o ile mnie pamięć nie zawodzi, poprzez przekształcenie kopca lub drzewa BST można uzyskać w dosyć szybkim czasie maksymalną liczbę w przedziale, jednak nie zdążyliśmy tego omówić, więc może się mylę. W każdym razie, doprecyzuję pytanie: jaki jest najszybszy algorytm na obliczenie maksymalnej liczby w przedziale?

P.S Sortowanie tablicy raczej odpada, bo trzeba sprawdzić przy okazji drugą pętla, czy dana liczba znajduje się w przedziale. Jeśli się mylę, proszę o poprawienie mnie.

0

Ależ masz rację, jeśli już masz całość w drzewie. Przypomnę tylko ze w pierwszym poście wyraźnie pytasz o:

w danym przedziale tablicy

Widzisz różnicę między nieposortowaną tablicą a drzewem binarnym? Bo ja widzę pesymistycznie O(n^2) czasu na zbudowanie drzewa. To juz by bylo lepiej to posortować w O(nlogn) a potem w O(logn) binarnie wyszukać interesującą cię wartość.
Więc moze sam wlożysz łaskawie wysiłek intelektualny i napiszesz co dokładnie masz dane?...

0

Racja, zupełnie zapomniałem, że drzewo i tablice to całkiem inne struktury danych. Dokładnie chodzi mi o to, aby w każdym momencie można było na wyciągnięcie ręki obliczyć maksimum w przedziale liczb, które są podane na wejściu. Tablica miała początkowo służyć do zachowania pierwotnej kolejności liczb. A przedział chcę wykorzystać do tego zadania: http://pl.spoj.pl/problems/FASTMAX/.

0

Shalom muszę Cię zmartwić ale można liniowo zbudować drzewo przedziałowe i następnie w czasie logarytmicznym wyszukiwać maksymalnego elementu z przedziału.
Po więcej informacji można się udać na stronkę http://was.zaa.mimuw.edu.pl/?q=node/8

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