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

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

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

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

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

Самому пока додуматься не удалось. Поиски повсюду приводят только к описанию упомянутого алгоритма — о доказательстве (или опровержении? хехе) его оптимальности ни полуслова...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.