Задача о наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Наибольшая возрастающая подпоследовательность строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k,  1 \le i_j \le n </tex> и  <tex> k </tex> - наибольшее из возможных.  
+
Наибольшая возрастающая подпоследовательность (''англ''. Longest increasing subsequence - LIS)  строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k,  1 \le i_j \le n </tex> и  <tex> k </tex> - наибольшее из возможных.  
 
}}
 
}}
 
Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность.
 
Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность.
 
Известно несколько алгоритмов решения этой задачи.
 
Известно несколько алгоритмов решения этой задачи.
 
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
 
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====

Версия 09:31, 27 ноября 2010

Определение:
Наибольшая возрастающая подпоследовательность (англ. Longest increasing subsequence - LIS) строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \le i_j \le n [/math] и [math] k [/math] - наибольшее из возможных.

Задача заключается в том, чтобы отыскать это наибольшее [math] k [/math] и саму подпоследовательность. Известно несколько алгоритмов решения этой задачи.

Пример алгоритма, работающего за время [math] O(n^2) [/math]