ADS úlohy E - podobne

Nejprve je potřeba si rozmyslet, zda přidání dalšího prvku na konec posloupnosti ovlivní dosavadní posloupnosti:

Budu-li postupovat v posloupnosti od konce do začátku, mohu najít první číslo, jehož rozdíl s posledním číslem přesáhne toleranci (

$k$). Pro další výpočty pak mi stačí uvažovat pouze úsek napravo od tohoto čísla. Zároveň je však potřeba si uvědomit, že i předposlední číslo již vyhradilo jakýsi úsek, ve kterém má smysl zkoumat podposloupnosti - budu se tak zabývat kratším z těchto úseků.

Nyní vezmu následující situaci: mám posloupnost

$P$ s finálním prvkem

$P_{n+1}$, pro nějž je zarážka na pozici

$s_1$.

Jelikož se jedná o první zarážku, celá posloupnost od

$0$ do

$n$ je platná a tuto posloupnost nelze rozšířit zleva ani zprava. Označím tak

$t_0=n$ a

$s_0=0$, což znamená, že podposloupnost má délku

$t_0-s_0$.

Dále, mezi

$P_{s+1}$ a

$P_{n+1}$ nevznikla žádná zarážka, a tak mohu postup opakovat (jako bych opět počítal od nuly), dokud nevznikne další zarážka.

Algoritmus (1):

Vstup: posloupnost

$P$ s prvky od

$0$ do

$n$, hranice

$k$.

1. $s_0=0$
2. $x=0$
3. Pro
   $u\in \{1\dots n\}$:
   1. Pro
      $v\in \{u-1\dots s_x\}:$
   2. Je-li
      $|P_u-P_v|>k$:
      1. $t_x=u$
      2. $x=x+1$
      3. $s_x=v+1$
      4. Ukonči cyklus
4. $t_x=n$
5. Najdi takové
   $s_x$, aby rozdíl
   $t_x-s_x$ byl co největší.
6. Výstup: Nejdelší posloupnost prvků
   $P_{s_x}\dots P_{t_x-1}$.

Zdůvodnění:

Algoritmus vlastně rozkouskuje interval na souvislé podposloupnosti, které již nejdou rozšířit. (nemusí být nutně disjunktní). Vybrat tu nejdelší nepředstavuje žádný problém.
Levá zarážka

$s_x$ (inkluzivní) vzniká tehdy, kdy zkoumané číslo

$P_u$ nelze odečíst od čísla před touto zarážkou - proto nelze posloupnost, ve které se nachází

$P_u$, rozšířit směrem doleva. Ze stejného důvodu se

$P_u$ stává pravou zarážkou (již nepatřící do ní) -

$t_x$ pro předchozí podposloupnost.

Složitost(1):

Pokud chci pouze nejdelší podposloupnost, pak mi stačí uchovávat si v paměti maximum a momentální podposloupnost, takže paměťové nároky budou konstantní. V opačném případě budu potřebovat lineární paměť na všechny zarážky.
Časová složitost závisí na tom, kolik budu mít zarážek. Nemám-li žádné, pak celá posloupnost je "v toleranci" a složitost tak bude kvadratická.

Optimalizace:

Nevznikne-li pro daný prvek

$P_u$ zarážka, pak pro následující prvky budu porovnávat rozdíl přes naprosto stejné prvky. Toto bych si mohl ušetřit tím, že pro daný interval zjistím maximum a minimum a budu porovnávat jen rozdíl mezi maximem a minimem.

Algoritmus(2):

Vstup: posloupnost

$P$ s prvky od

$0$ do

$n$, hranice

$k$.

1. $s_0=0$
2. $x=0$
3. $maxim=-\mathrm{\infty },minim=+\mathrm{\infty }$
4. $d=0$
5. $z=true$
6. Pro
   $u\in \{1\dots n\}$:
   1. Je-li
      $z=false$ a je-li
      $|P_u-maxim|\le k$ a
      $|P_u-minim|\le k$:
      2.
      $maxim=Max(P_u,maxim)$
      3.
      $minim=Min(P_u,minim)$
      4. Pokračuj dále
   2. Jinak (je potřeba vytvořit zarážku):
   3. $z=false$
   4. Pro
      $v\in \{u-1\dots s_x\}:$
   5. Je-li
      $|P_u-P_v|>k$:
      1. $z=true$
      2. $t_x=u$
      3. $x=x+1$
      4. $s_x=v+1$
      5. $maxim=Max(P_{s_x}\dots P_u)$
      6. $minim=Min(P_{s_x}\dots P_u$
      7. Ukonči cyklus
7. $t_x=n$
8. Najdi takové
   $s_x$, aby rozdíl
   $t_x-s_x$ byl co největší.
9. Výstup: Nejdelší posloupnost prvků
   $P_{s_x}\dots P_{t_x-1}$.

Složitost (2):

Paměťová složitost výše popsaného je

$O(n)$, pokud již zaznamenávám maximum, pak

$O(1)$.

Co se týče časové složitosti: Pouhé rozšíření posloupnosti (nový prvek se vleze do tolerance maxima i minima) má složitost O(1). V případě, že je potřeba posloupnost uzavřít, může být opět potřeba prohledat

$O(n)$ prvků, levá zarážka se posune o jeden prvek, a tak složitost v nejhorším případě by stále byla

$O(n^2)$.