[Algorytmy] Znajdowanie najbliższego mniejszego elementu

[diana20]

Proszę o pomoc w rozwiazaniu zadania i wyjaśnienie krok po kroku tego rozwiązania.

Dany jest n-elementowy ciąg \(\displaystyle{ e[1],....,e[n]}\) liczb rzeczywistych. Zaproponuj
algorytm, który dla każdego elementu \(\displaystyle{ e}\) wyznaczy pozycję najbliższgo z lewej elementu mniejszego od \(\displaystyle{ e}\).

Rozwiązanie powinno zawierać
specyfikację zadania,
opis słowny metody rozwiązania,
algorytm rozwiązujący (ew. jego implementację),
analizę kosztu i
analizę poprawności względem podanej specyfikacji.

[lukasz93a]

Kod: Zaznacz cały

for(i=0; i<n;i++)
{
    for(k=i-1; k>0;k--)
    {
        if(e[k]<e[i])
            przypisanie e[k] do e[i];
    }
}

[Xitami]

jest
for(i=0; i < n;i++) a powinno być
for(i=2; i<=n;i++)
2 to drobiazg, nieostrość bardzo istotna

ale co zrobić z e[1] i z takimi e, dla których gdy j<i e[j]>=e ?

[lukasz93a]

ale co zrobić z e[1] i z takimi e, dla których gdy j<i e[j]>=e ?

Jeśli e[1] > e to nie ma takiego elementu.
Jeśli e[j]>e to pętla zmniejsza j o -1 i sprawdza dalej.

Do do i=2 co będzie gdy ciąg będzie jednoelementowy?

[Xitami]

Do do i=2 co będzie gdy ciąg będzie jednoelementowy?

Racja !
czyli niby for(i=1; i<=n;i++)
ale czy wtedy istnieje mniejszy od e[1]?

I co w ogóle zrobić gdy brak (a mamy znaleźć dla każdego)?

[lukasz93a]

Oczywiście wtedy nie ma takiego elementu.
Po prostu trzeba wypisać, że nie ma takiego elementu i już. Nic się nie da z tym zrobić.

To jaki będzie rezultat zależy właśnie od ciągu. Jeżeli zostanie podany taki, że dla każdego e istnieje mniejszy element to program go przypisze jeśli nie istnieje to nie przypisze nic.

Domyślnie przy tworzeniu struktury ciągu (przed przystąpieniem do sprawdzania mniejszych elementów) w programie powinno się każdemu e przypisać właśnie brak elementu mniejszego.

[marcin_smu]

Da się to zrobić w dużo lepszej złożoności tj. w \(\displaystyle{ O(n)}\).

Kod: Zaznacz cały

w[1]=-1;
for(int i=2;i<=n;i++){
  int ak=i-1;
  while(ak!=-1&&e[ak]>=e[i])
    ak=w[ak];
  w[i]=ak;
}

\(\displaystyle{ w}\) jest równe indeksowi przyporządkowanego elementu dla \(\displaystyle{ e}\) lub \(\displaystyle{ -1}\), gdy nie przyporządkowujemy żadnego elementu. Rozwiązanie to korzysta z dość prostej obserwacji, że jeśli dla danego \(\displaystyle{ e}\) sprawdziliśmy, że dany element \(\displaystyle{ ak}\) jest zbyt duży to wszystkie na lewo od \(\displaystyle{ ak}\) nie mniejsze od niego są również za duże, więc możemy od razu przejść do sprawdzania pierwszego mniejszego od \(\displaystyle{ ak}\), do którego odnośnik już wcześniej policzyliśmy.
W analizie złożoności dla ułatwienia przepisze kod z dodatkową zmienną \(\displaystyle{ t}\).

Kod: Zaznacz cały

w[1]=-1;
int t=0;
for(int i=2;i<=n;i++){
  int ak=i-1;
  t++;
  while(ak!=-1&&e[ak]>=e[i]){
    ak=w[ak];
    t--;
  }
  w[i]=ak;
}

Nietrudno dowieść, że zmienna \(\displaystyle{ t}\) wyraża ilość wywołań wnętrza pętli \(\displaystyle{ while}\) potrzebnych do tego, aby \(\displaystyle{ ak}\) przyjęło wartość \(\displaystyle{ -1}\). Czyli w szczególności \(\displaystyle{ t}\) jest zawsze nieujemne. Zwiększamy je co najwyżej \(\displaystyle{ O(n)}\) razy, więc zmniejszymy je również co najwyżej \(\displaystyle{ O(n)}\) razy. Złożoność naszego rozwiązania amortyzuje się więc do \(\displaystyle{ O(n)}\).