Здравствуйте, bzig, писал (в коллеги улыбнитесь)

Автор: bzig
Дата: 08.11.18

:

B>Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.

Является ли задача NP-полной?
Существуют ли решения быстрее O(2^n) по времени?, O(n^2)?, O(n*log(n))?

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, bzig, писал (в коллеги улыбнитесь)

Автор: bzig
Дата: 08.11.18

:

B>>Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.

C>Существуют ли решения быстрее O(2^n) по времени?, O(n^2)?, O(n*log(n))?

Удалить наименьший список == оставить больше элементов: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Здравствуйте, Chorkov, Вы писали:

B>>Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.

C>Является ли задача NP-полной?
C>Существуют ли решения быстрее O(2^n) по времени?, O(n^2)?, O(n*log(n))?


Ну, очевидно, что за О( n log n ) задача переводится в "есть перестановка чисел от 1 до N, вычеркнуть как можно меньше чисел, что бы оставшаяся последовательность была отсортированной"


А эта задача очевидно решается не дольше, чем за O( n^2 ) при помощи динамического программирования функции:
предыдущий элемент самой длинной подпоследовательности первых k элементов данной последовательности, не превосходящий l