Давайте рассмотрим следующую проблему: вам дан список чисел, и вы хотите найти самую длинную подпоследовательность этого списка, где числа расположены в порядке возрастания.Например, учитывая последовательность
2 7 1 8 3 9 4 5 0 6
, вы можете сформировать подпоследовательность [2, 7, 8, 9] следующим образом:
2 7 1 8 3 9 4 5 0 6
^ ^ ^ ^
, но есть еще более длинная, [1, 3, 4, 5, 6] доступно здесь:
2 7 1 8 3 9 4 5 0 6
^ ^ ^ ^ ^
Это самая длинная подпоследовательность в возрастающем порядке, я считаю, хотя, пожалуйста, дайте мне знать, если я ошибаюсь.
Теперь, когда у нас есть эта проблема, как мы будем решать ее в общем случае, когда у вас есть список из n чисел?Начнем с не очень хорошего варианта.Одной из возможностей будет перечислить все подпоследовательности исходного списка чисел, затем отфильтровать все, что не в порядке возрастания, а затем выбрать самый длинный из всех найденных нами.Например, учитывая этот короткий список:
2 7 1 8
мы сформируем все возможные подпоследовательности, которые показаны здесь:
- []
- [8]
- [1]
- [1, 8]
- [7]
- [7, 8]
- [7,1]
- [7, 1, 8]
- [2]
- [2, 8]
- [2, 1]
- [2, 1, 8]
- [2, 7]
- [2, 7, 8]
- [2, 7, 1]
- [2, 7, 1, 8]
Да, этот список довольно длинный.Но, взглянув на это, мы увидим, что самые длинные растущие подпоследовательности имеют длину два, и есть множество вариантов, из которых мы можем выбрать один.
Теперь, насколько хорошо это будет масштабироваться как наш входсписок становится длиннее и длиннее?Вот о чем подумать - сколько подпоследовательностей существует в этом новом списке, который я сделал, добавив 3 в конец существующего списка?
2 7 1 8 3
Что ж, каждая существующая подпоследовательность все еще является совершенно допустимой подпоследовательностьюВот.Но вдобавок ко всему, мы можем сформировать кучу новых подпоследовательностей.Фактически, мы могли бы взять любую существующую подпоследовательность и затем прикрепить 3 к концу.Это означает, что если бы у нас было S подпоследовательностей для нашего списка длины четыре, у нас будет 2S подпоследовательности для нашего списка длины пять.
В целом, вы можете увидеть, что если вы возьмете список и добавите еще одинэлемент в конце этого, вы удвоите количество доступных подпоследовательностей.Это математический факт, и он не является ни хорошим, ни плохим сам по себе, но если мы занимаемся перечислением всех этих подпоследовательностей и проверкой каждой из них, чтобы увидеть, имеет ли она какое-то свойство, мыбудет в беде, потому что это означает, что будет множество подпоследовательностей.Мы уже видим, что существует 16 подпоследовательностей в четырехэлементном списке.Это означает, что есть 32 подпоследовательности списка из пяти элементов, 64 подпоследовательности списка из шести элементов и, в более общем случае, 2 n подпоследовательности списка из n элементов.
С этимпонимание, давайте сделаем быстрый расчет.Сколько подпоследовательностей нам придется проверить, если у нас есть, скажем, список из 300 элементов?Мы должны были бы потенциально проверить 2 300 из них - число, которое больше, чем число атомов в наблюдаемой вселенной!К сожалению.Это займет намного больше времени, чем у нас.
С другой стороны, есть прекрасный алгоритм, называемый сортировка по терпению , который всегда найдет самую длинную возрастающую подпоследовательность и который делает это довольно легко.,Вы можете сделать это, играя в небольшую игру.Вы поместите каждый из элементов в списке в одну из множества куч.Чтобы определить, какую колоду выбрать, найдите первую стопку, чей верхний номер больше указанного числа, и поместите ее сверху.Если вы не можете найти стопку таким образом, поместите число в собственную стопку справа.
Например, с учетом этого оригинального списка:
2 7 1 8 3 9 4 5 0 6
после игрымы бы в конечном итоге с этими кучами:
0
1 3 4 5
2 7 8 9 6
И вот удивительный факт: количество используемых стопок равно длине самой длинной увеличивающейся подпоследовательности. Кроме того, вы можете найти эту подпоследовательность следующим образом: каждый раз, когда вы помещаете число поверхстопка, запишите номер, который был сверху стопки слева от нее.Если мы сделаем это с приведенными выше числами, вот что мы найдем;число в скобках говорит нам, что находилось на вершине стека слева в то время, когда мы записывали число:
0
1 3 (1) 4 (3) 5 (4)
2 7 (2) 8 (7) 9 (8) 6 (5)
Чтобы найти необходимую последовательность, начните с вершины самой левой стопки.Запишите это число, затем найдите число в скобках и повторите этот процесс.Делая это здесь, мы получаем 6, 5, 4, 3, 1, который, если обратить вспять, равен 1, 3, 4, 5, 6, самая длинная возрастающая подпоследовательность!(Вау!) Вы можете доказать, что это работает во всех случаях, и это действительно прекрасное упражнение, чтобы действительно пойти и сделать это.
Так что теперь вопрос в том, насколько быстрым этот процесс.Размещение первого числа занимает одну единицу работы - просто поместите его в свою стопку.Размещение второго числа занимает максимум две единицы работы - мы должны взглянуть на верхнюю часть первой стопки и, необязательно, поместить число во вторую стопку.Для размещения третьего числа требуется не более трех единиц работы - нам нужно рассмотреть до двух стопок и, возможно, поместить число в свою третью стопку.В более общем смысле размещение k-го числа занимает k единиц работы.В целом это означает, что работа, которую мы выполняем, примерно равна
1 + 2 + 3 + ... + n
, если у нас есть n элементов.Это известная сумма, называемая суммой Гаусса, и она упрощается примерно до n 2 / 2. Таким образом, мы можем сказать, что нам нужно выполнить примерно n 2 / 2 единиц работы, чтобырешить все так.
Как это можно сравнить с нашим решением 2 n , которое было раньше?Ну, в отличие от 2 n , который тупо быстро растет как функция от n, n 2 / 2 на самом деле довольно хорошая функция.Если мы добавим n = 300, что ранее в 2 n land вернуло «количество атомов во вселенной», мы получим более скромные 45 000.Если это количество наносекунд, это ничего не значит;это займет компьютер меньше секунды, чтобы сделать.На самом деле, вам нужно подключить довольно большое значение n, прежде чем вы посмотрите на что-то, что может потребоваться компьютеру для завершения.
Функция n 2 /2 имеет интересное свойство по сравнению с 2 n .При 2 n , если вы увеличите n на единицу, как мы видели ранее, 2 n удвоится.С другой стороны, если вы возьмете n 2 / 2 и увеличите n на единицу, то n 2 / 2 увеличится, но не намного (в частности, на n + 1/2).
Для сравнения: если взять 2 n , а затем double n, то 2 n squares по размеру - yikes!Но если вы возьмете n 2 / 2 и удвоите n, тогда n 2 / 2 увеличится только в четыре раза - на самом деле, не так уж и плохо, учитывая, что мы удвоили наш вкладразмер!
В этом суть того, о чем вы упоминали.Алгоритмы с такими временами выполнения, как 2 n , n !, и т. Д. Масштабируют ужасно как функцию n, поскольку увеличение n на единицу вызывает огромный скачок во время выполнения,С другой стороны, такие функции, как n, n log n, n 2 и т. Д., Имеют свойство, заключающееся в том, что при удвоении n время выполнения увеличивается только на некоторый постоянный член.Поэтому они гораздо лучше масштабируются как функция ввода.