Najdłuższy zmienny podsekwencja

W matematyce kombinatorycznej , prawdopodobieństwie i informatyce w problemie najdłuższego podciągu naprzemiennego chce się znaleźć podciąg danego ciągu , w którym elementy są ułożone naprzemiennie i w którym ciąg jest jak najdłuższy.

Formalnie $_$ _ sekwencja różnych liczb rzeczywistych, a następnie podsekwencja ${\ Displaystyle \ {x_ {i_ {1}}, x_ {i_ {2}}, \ ldots, x_ { i_{k}}\}}$ jest naprzemienne (lub zygzakowate lub dół-góra ) jeśli

${\ Displaystyle x_ {i_ {1}}> x_ {i_ {2} <x_ {i_ {3}}> \ cdots x_ {i_ {k}} \ qquad {\ tekst {i}} \ qquad 1 \ równoważnik i_{1}<i_{2}<\cdots <i_{k}\równ.}$

Podobnie, jest odwrotnie naprzemiennie (lub góra-dół ), jeśli ${\ Displaystyle \ mathbf {x}}$

${\ Displaystyle x_ {i_ {1}}<x_ {i_ {2}}> x_ {i_ {3}}< \ cdots x_ {i_ {k}} \ qquad {\ tekst {i}} \ qquad 1 \ równoważnik i_{1}<i_{2}<\cdots <i_{k}\równ.}$

Niech za ${x})}$ oznacza długość (liczbę wyrazów) najdłuższego naprzemiennego podciągu ${\ Displaystyle \ mathbf { x} }$ . Na przykład, jeśli weźmiemy pod uwagę niektóre permutacje liczb całkowitych 1,2,3,4,5, mamy to

• ${\ Displaystyle {\ rm {jak}} _ {5} (1,2,3,4,5) = 2}$ ; ponieważ każda sekwencja 2 różnych cyfr jest (z definicji) naprzemienna. (na przykład 1,2 lub 1,4 lub 3,5);
• ${\ Displaystyle {\ rm {jak}} _ {5} (1,5,3,2,4) = 4,}$ ponieważ 1,5 ,3,4 i 1,5,2,4 i 1,3,2,4 są naprzemienne i nie ma naprzemiennego podciągu z większą liczbą elementów;
• ${\ Displaystyle {\ rm {jak}} _ {5} (5,3,4,1,2) = 5,}$ ponieważ 5,3 ,4,1,2 samo jest naprzemienne.

Wydajne algorytmy

Najdłuższy problem z naprzemiennymi podsekwencjami można rozwiązać $w$$czasie$ gdzie oryginalnej

Wyniki dystrybucyjne

x ${\ Displaystyle \ mathbf {x}}$ losową permutacją liczb całkowitych ${\ Displaystyle 1,2, \ ldots, n}$ i ${\ Displaystyle A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )}$ , to można pokazać, że

${\ Displaystyle E [A_ {n}] = {\ Frac {2n} {3}} + {\ Frac {1} {6}} \ qquad {\ tekst {i}} \ qquad \ nazwa operatora {Var} [A_ {n}]={\frac {8n}{45}}-{\frac {13}{180}}.}$

Ponadto, gdy $.$$odpowiednio wyśrodkowana i przeskalowana$ , standardowego rozkładu

Algorytmy internetowe

Najdłuższy problem podsekwencji naprzemiennej został również zbadany w ustawieniach algorytmów online , w których elementy są prezentowane w trybie online, a decydent musi zdecydować, czy uwzględnić, czy wykluczyć ${\ displaystyle \ mathbf {x}}$ każdego elementu w momencie jego pierwszej prezentacji, bez wiedzy o elementach, które zostaną zaprezentowane w przyszłości i bez możliwości przypomnienia sobie wcześniejszych obserwacji.

$uwagę$ sekwencję $_$ _ _ możliwe jest skonstruowanie procedury selekcji, która maksymalizuje oczekiwaną liczbę naprzemiennych selekcji. Takie oczekiwane wartości można ściśle oszacować i wynosi to ${\ Displaystyle (2- {\ sqrt {2}}) n + O (1)}$ .

Ponieważ ${\ displaystyle n \ rightarrow \ infty}$ , optymalna liczba naprzemiennych wyborów online odpowiednio wyśrodkowanych i przeskalowanych zbiega się do rozkładu normalnego.

Zobacz też

• Permutacja naprzemienna
• Wzorzec permutacji i unikanie wzorca
• Zliczanie lokalnych maksimów i/lub lokalnych minimów w danej sekwencji
• Testy punktu zwrotnego do testowania statystycznej $obserwacji$
• Liczba przebiegów naprzemiennych
• Najdłuższy rosnący podciąg
• Najdłuższy wspólny problem podciągu