Нижняя граница сложности известной задачи (см. внутри).
От: Аноним  
Дата: 08.06.05 01:00
Оценка:
Здравствуйте, господа.

"Известная задача" — поиск возрастающей подпоследовательности максимальной длины в данном массиве.

Иначе говоря, дан массив "чисел" длины N; требуется в другой массив записать возрастающий набор элементов этого массива с возрастающими индексами, имеющий наибольшую длину, и выдать эту длину. Под "числами" понимаются элементы, над которыми допустимы только операции копирования и сравнения — фактически, элементы линейно упорядоченного множества.

Хорошо известно, что существует алгоритм, решающий задачу за количество сравнений порядка N*log(N).

Вопрос — является ли он асимптотически оптимальным (по N)?

Самому пока додуматься не удалось. Поиски повсюду приводят только к описанию упомянутого алгоритма — о доказательстве (или опровержении? хехе) его оптимальности ни полуслова...
Re: Неужели всё так плохо?
От: Аноним  
Дата: 09.06.05 23:56
Оценка:
Ну нигде не могут ответить на этот вопрос.

И всё-таки таким уж сложным он мне определённо не кажется. Если сравнить с классикой — оценкой снизу числа сравнений для задачи сортировки — то вроде отличие должно быть незначительным. Уж явно не в категории оценок сложностей арифметических задач...
Re[2]: Неужели всё так плохо?
От: _DAle_ Беларусь  
Дата: 10.06.05 17:38
Оценка: 10 (1)
Здравствуйте, <Аноним>, Вы писали:

А>Ну нигде не могут ответить на этот вопрос.


А>И всё-таки таким уж сложным он мне определённо не кажется. Если сравнить с классикой — оценкой снизу числа сравнений для задачи сортировки — то вроде отличие должно быть незначительным. Уж явно не в категории оценок сложностей арифметических задач...


Цитата из http://www.ime.usp.br/~is/papir/sctp/node2.html

...Then an lcs is just a longest increasing subsequence of the second permutation and this problem is part of a very rich theory of representations of the symmetric group using Young tableaux extensively studied by A. Young, G de B. Robinson, C. E. Schensted and M. P. Schutzenberger. A survey focusing on the computational aspects can be found in Knuth's book [26] from which Fredman [14] extracted an algorithm to solve the longest increasing subsequence problem. His algorithm runs in time O(n*logn) and he also derives n*logn as a lower bound for the problem.


Если недостаточно, то можно попробовать поискать непосредственное доказательство.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
Re[3]: Отлично - то, что надо.
От: Аноним  
Дата: 10.06.05 19:06
Оценка:
По крайней мере теперь понятно, откуда отталкиваться. Спасибо!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.