Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о связи длины НВП и НУП)
Строка 36: Строка 36:
 
|about=
 
|about=
 
|statement=
 
|statement=
Пусть <tex>a</tex> - последовательность чисел длины <tex>n, l</tex> - длина наибольшей возрастающей подпоследовательности (НВП), <tex>k</tex> - длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.
+
Пусть <tex>a</tex> - перестановка чисел длины <tex>n, l</tex> - длина наибольшей возрастающей подпоследовательности (НВП), <tex>k</tex> - длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.
  
 
|proof=
 
|proof=

Версия 11:23, 25 декабря 2010

Последовательность — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.

Определения

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется неубывающей, если каждый элемент этой последовательности не превосходит следующего за ним.

[math]\{x_n\}[/math]неубывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}[/math]


Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется невозрастающей, если каждый следующий элемент этой последовательности не превосходит предыдущего.

[math]\{x_n\}[/math]невозрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}[/math]


Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется возрастающей, если каждый следующий элемент этой последовательности превышает предыдущий.

[math]\{x_n\}[/math]возрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \lt x_{n+1}[/math]


Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется убывающей, если каждый элемент этой последовательности превышает следующий за ним.

[math]\{x_n\}[/math]убывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \gt x_{n+1}[/math]


Последовательность называется монотонной, если она является неубывающей, либо невозрастающей.

Последовательность называется строго монотонной, если она является возрастающей, либо убывающей.

Очевидно, что строго монотонная последовательность является монотонной.

Теорема о связи длины НВП и НУП

Теорема:
Пусть [math]a[/math] - перестановка чисел длины [math]n, l[/math] - длина наибольшей возрастающей подпоследовательности (НВП), [math]k[/math] - длина наибольшей убывающей подпоследовательности (НУП). Тогда [math]l k \geqslant n[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим два массива длины [math]n : S [/math] и [math] T [/math], где [math] S_i [/math] - длина НВП, которая заканчивается на [math]a_i[/math], [math] T_i [/math] - длина НУП, которая начинается на [math]a_i[/math].

Докажем, что все пары [math](S_i, T_i)[/math] различны. Пусть существуют такие [math]i \lt j[/math] , что [math] S_i [/math] = [math] S_j [/math] и [math] T_i [/math] = [math] T_j[/math]. Если [math]a_i \lt a_j[/math], тогда [math] a_j [/math] можно добавить к НВП, заканчивающейся на [math] a_i [/math], следовательно [math]S_j \geqslant S_i + 1[/math]. Если [math]a_i \gt a_j[/math], то по аналогии [math]T_i \geqslant T_j + 1[/math]. Противоречие! Следовательно все такие пары различны.

Заметим что [math]1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k[/math], поэтому существуют [math]l k[/math] различных пар [math] (S_i, T_i) [/math]. Если [math]l k \lt n[/math] тогда среди [math] n [/math] пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. [math]l k \geqslant n[/math], ч. т. д.
[math]\triangleleft[/math]

Следствие из теоремы

Утверждение:
Пусть [math]n[/math] - длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше [math]\sqrt{n}[/math]

Источники