[Algorytmy] Zliczenie elementów tablicy
[Algorytmy] Zliczenie elementów tablicy
Mam problem! Chcę znaleźć metodę na policzenie liczby elementów w tablicy, aby koszt w najgorszym przypadku był \(\displaystyle{ \log n}\). Dokładniej: w zadaniu mam posortowaną tablicę (załóżmy, że rosnąco) i np. dla tablicy o elementach: \(\displaystyle{ 1,3,5,5,5,5,6,7,8,9}\) chcę się dowiedzieć ile jest elementów \(\displaystyle{ x=5}\) w tej tablicy. Zastosowałam wyszukiwanie binarne, gdyż takie szukanie daje mały koszt, tylko nie wiem jak zliczyć ile jest tych elementów. Próbowałam już chyba wszystkiego, ale w każdym przypadku koszt wzrasta, a ja chce, żeby koszt był logarytmiczny. Może w złą stronę się kieruje, może nie powinnam stosować binarnych poszukiwań? Proszę o pomoc w znalezieniu metody, algorytm myślę, że dam rade napisać, jeżeli już będę wiedziała jak postępować.
Ostatnio zmieniony 11 lis 2012, o 09:24 przez Afish, łącznie zmieniany 2 razy.
Powód: "Ilość" stosuje się tylko do rzeczowników niepoliczalnychStaraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex]
Powód: "Ilość" stosuje się tylko do rzeczowników niepoliczalnychStaraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach
-
abc666
[Algorytmy] Zliczenie elementów tablicy
Poszukaj pierwszego wystąpienia 5, a potem ostatniego. Policz o ile różni się pozycja.