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

 

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

Автор: admin от 27-11-2017, 10:15, посмотрело: 75

Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности Содержание:



Последовательность Фибоначчи O (n)

Решение за O(n ^ 2)

Бинарный поиск O(log n)

Решение за O(n * log n)



Задача



"Найти длину самой большой возрастающей подпоследовательности в массиве."



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



На пальцах



Есть последовательность:



5, 10, 6, 12, 3, 24, 7, 8



Вот примеры подпоследовательностей:



10, 3, 8

5, 6, 3



А вот примеры возрастающих подпоследовательностей:



5, 6, 7, 8

3, 7, 8



А вот примеры возрастающих подпоследовательностей наибольшей длины:



5, 6, 12, 24

5, 6, 7, 8

Последовательность Фибоначчи популярна и окружена легендами, разглядеть ее пытаются (и надо признать, им это удается) везде, где только можно. Принцип же ее прост. n-ый элемент последовательности равен сумме n-1 и n-2 элемента. Начинается соответственно с 0 и 1.



0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …



Берем 0, прибавляем 1 — получаем 1.

Берем 1, прибавляем 1 — получаем 2.

Берем 1, прибавляем 2 — получаем, ну вы поняли, 3.



Собственно нахождение n-го элемента этой последовательности и будет нашей задачей. Решение кроется в самом определении этой последовательности. Мы заведем один мутабельный массив, в который будем сохранять промежуточные результаты вычисления чисел Фибоначчи, т.е. те самые n-1 и n-2.



Псевдокод:



int numberForIndex(int index) {

   int[] numbers = [0, 1];

    for (int i = 2; i < index + 1; i++) {
        numbers[index] = numbers[i - 1] + numbers[i - 2];
    }

    return numbers[index];
}


Пример решения на Objective-C



Тесты



Вот и всё, в этом массиве numbers вся соль ДП, это своего рода кэш (Caсhe), в который мы складываем предыдущие результаты вычисления этой же задачи, только на меньшей размерности (n-1 и n-2), что дает нам возможность за одно действие найти решение для размерности n.



Этот алгоритм работает за O(n), но использует немного дополнительной памяти — наш массив.



Вернемся к нахождению длины максимальной возрастающей подпоследовательности.



Реализация на Objective-C

Тесты



Вы не могли не заметить два вложенных цикла в коде, а там где есть два вложенных цикла проходящих по одному массиву, есть и квадратичная сложность O(n^2), что обычно не есть хорошо.



Теперь, если вы билингвал, вы несомненно зададитесь вопросом “Can we do better?”, обычные же смертные спросят “Могу ли я придумать алгоритм, который сделает это за меньшее время?”



Ответ: “да, можете!”



Чтобы сделать это нам нужно вспомнить, что такое бинарный поиск.Бинарный поиск работает только на отсортированных массивах. Например, нам нужно найти позицию числа n в отсортированном массиве:

1, 5, 6, 8, 14, 15, 17, 20, 22



Зная что массив отсортирован, мы всегда можем сказать правее или левее определенного числа в массиве искомое число должно находиться.



Мы ищем позицию числа 8 в этом массиве. С какой стороны от середины массива оно будет находиться? 14 — это число в середине массива. 8 < 14 — следовательно 8 левее 14. Теперь нас больше не интересует правая часть массива, и мы можем ее отбросить и повторять ту же самую операцию вновь и вновь пока не наткнемся на 8. Как видите, нам даже не нужно проходить по всем элементам массива, сложность этого алгоритма < O( n ) и равна O (log n).



Для реализации алгоритма нам понадобятся 3 переменные для индексов: left, middle, right.



Ищем позицию числа 8.



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

Мы отгадали где находится 8 с трёх нот.





Реализация на Objective-C

Тесты



Итоги



Мы с вами сейчас рассмотрели 4 алгоритма разной сложности. Это сложности, с которыми вам приходится встречаться постоянно при анализе алгоритмов:



О( log n ), О( n ), О( n * log n ), О( n ^ 2 )



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

Эта картинка из вот этой статьи



Еще мы рассмотрели примеры использования Динамического Программирования, тем самым расширив наш инструмент разработки и понимания алгоритмов. Эти принципы пригодятся вам при изучении других проблем.



Для лучшего понимания я рекомендую вам закодировать эти проблемы самим на привычном вам языке. А еще было бы здорово, если бы вы запостили ссылку на ваше решение в комментах.



Еще предлагаю подумать над тем как доработать последний алгоритм за O (n * log n ) так чтобы вывести еще и саму наибольшую подпоследовательность. Ответ напишите в комментах.



Всем спасибо за внимание, до новых встреч!



Ссылки:



Вопрос на Stackoverflow.com

Примеры реализации на C++ и Java

Видео с объяснением



Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *