Сокращение и поиск | Обзор анализа сложности
Слово « обрезать » означает уменьшить что-то, удалив то, что не нужно. Итак, Prune-and-Search — отличная алгоритмическая парадигма для решения различных оптимизационных задач. Этот подход был впервые предложен Нимродом Мегиддо в 1983 году . Этот подход всегда состоит из нескольких итераций. На каждой итерации он отбрасывает часть входных данных, скажем, f, а затем рекурсивно вызывает тот же алгоритм для оставшихся данных, чтобы решить проблему.
Основная идея этого подхода состоит в том, чтобы уменьшить область поиска путем сокращения части входных элементов и рекурсии на оставшихся допустимых входных элементах . После некоторых итераций размер входных данных станет настолько мал, что его можно будет решить методом грубой силы за постоянное время c'.
Анализ временной сложности для таких алгоритмов:
Пусть время, необходимое для каждой итерации, равно O(n^k) , где:
n = size of input data k is some constant.
Пусть f = доля данных, удаляемых на каждой итерации. Рекурсивно описанный выше подход можно записать как
T(n) = T((1-f)n) + O(n^k)
We have,
T(n) <= T((1-f)n) + c*n^k for very large value of n.
<= T((1-f)^2 * n) + c*n^k +c*((1-f)^k)*n^k
.
.
<= c’ + c*n^k + c*((1-f)^k)n^k + c*((1-f)^2k)n^k + ….. + c*((1-f)^pk)n^k
= c’ + c*n^k(1 + (1-f)^k + (1-f)^2k + ….. + (1-f)^pk).
Since (1-f) < 1, as n tends to very large number
Therefore, T(n) = O(n^k).
Он показывает, что временная сложность всего процесса того же порядка, что и временная сложность операции «вырезать и искать» в каждой итерации. Этот подход можно использовать для анализа алгоритмов многих известных задач, таких как бинарный поиск, поиск K-го наибольшего/наименьшего элемента из несортированного массива (проблема выбора), задача с 1 центром (наименьший охватывающий круг), решение линейного программирования с двумя переменными, и так далее.
Примеры:
1. Бинарный поиск:
Как мы знаем, этот метод применяется к отсортированному списку данных для поиска индекса определенного значения (скажем, « val ») в данном списке. Для этого переходим к среднему элементу и сравниваем его с val . Если средний элемент равен val , мы возвращаем этот средний элемент. В противном случае мы сокращаем половину данных, и тот же метод используется для остальных элементов. Подробную реализацию смотрите здесь.
Анализ временной сложности:
На каждом шаге, поскольку он сравнивает val только со средним элементом, поэтому сложность для этого шага будет O (1) , скажем, c (любая константа). И половина списка удаляется, поэтому T(n) = T(n/2) + O(1), если n>=2 В противном случае T(n) = O(1) = c .
In simple terms,
T(n) = T(n/2) + c
= T(n/4) + c + c
= T(n/8) + c + c + c
…..
= T(1) + c + … + c + c
= k times c where k will be a constant.
Since half of input is discarded in each iteration, so the value of k will be at most log(n) in worst cases. Therefore, worst case complexity of Binary Search will be
T(n) = O(log(n)).
2. Проблема выбора:
Учитывая неупорядоченный список из n элементов, задача состоит в том, чтобы найти K-й наименьший элемент из списка. Первый очень простой подход состоит в том, чтобы отсортировать данный список в порядке возрастания и напрямую выбрать значение по индексу K. Таким образом, сортировка займет O (n * log (n)) времени в целом и O (1) для получения значения K-го индекса. Следовательно, в целом T(n) = O(n*log(n)) для этого подхода.
Второй подход заключается в использовании метода QuickSelect, т. е. метода удаления и поиска. Основная идея этого алгоритма выбора с отсечением и поиском состоит в том, чтобы определить долю, которая не будет содержать K-й элемент, и отбросить эту часть элементов из следующих итераций. Мы знаем, что для того, чтобы иметь алгоритм O(n) , у нас должен быть метод, способный отбрасывать часть элементов за время O(n) на каждой итерации. Пусть P — элемент списка, который может разделить данный список на две части, скажем, S1 и S2 , так что S1 содержит все элементы, меньшие или равные P , а S2 содержит все элементы, большие P. Теперь мы можем сказать, что
- Если |S1| == K , то S1[k] будет K-м наименьшим элементом.
- Если |S1| > K , то K-й элемент должен присутствовать в S1 . Поэтому отбросьте вторую часть S2 и рекурсивно повторите S1 с тем же алгоритмом.
- В противном случае K-й элемент должен находиться в S2 . Поэтому отбросьте S1 и выполните рекурсию по S2 для (K-|S1|)-го элемента в S2 .
Ключевым моментом здесь является то, как выбрать P так, чтобы мы всегда могли отбросить часть S, независимо от того, сокращаем ли мы S1 или S2 . Ответ: P должен быть медианой списка S. Опять же, нахождение медианы является частным случаем этой проблемы, когда K=n/2 .
Но медиану можно вычислить другим способом, более эффективно, используя следующий алгоритм:
- Разделите список на n/5 подсписков, каждый из которых содержит не более 5 элементов.
- Теперь мы можем отсортировать каждый подсписок и найти их медиану за постоянное время.
- Снова найдите медиану всех медиан рекурсивно, пока размер не станет не более 5. Полученная медиана будет идеальной точкой опоры для использования в алгоритме быстрого выбора. [Обратите внимание, что сортировка вставками будет лучшим выбором для сортировки меньших подсписков размера 5. .]
Почему только 5?
Разделение списка на размер 5 предполагает наихудшее разделение 70-30. По крайней мере, половина медиан больше, чем медиана медиан, поэтому половина блоков n/5 имеет по крайней мере 3 элемента, которые дают разбиение 3n/10, что означает, что другое разбиение равно 7n/10 в худшем случае, т. е. T(n ) = Т(n/5) + T(7n/10) + O(n). Поскольку (n/5 + 7n/10) < 1, значит, T(n) = O(n) в худшем случае. Пусть P будет медианой медиан, которую можно представить как:
|1""1""1""1""1| 1 1 1 1 |2 2 2 2 2| 2 2 2 2 |3__3__3__3_|P|"3""3""3""3| 4 4 4 4 |4 4 4 4 4| 5 5 5 5 |5__5__5__5__5|
Как показано здесь, по крайней мере одна четверть элементов в S меньше или равна P и по крайней мере одна четверть элементов S больше или равна P. Таким образом, если мы выбираем P таким образом, мы всегда можем удалить по крайней мере одну четвертую часть элементов на каждой итерации. Следовательно, разбиение S на подсписки размера 5 будет эффективным способом найти медиану медиан. Теперь мы можем сформулировать алгоритм так:
Prune-and-Search Algorithm to find Kth smallest element
Input: A set S of n elements and K.
Output: The Kth smallest element in S.
Approach:
Step-1: If |S| <= 5, apply any Brute Force method.
Step-2: Divide S into n/5 sublists each containing at most 5 elements.
Step-3: Sort each sublists(Insertion sort will be better one to apply).
Step-4: Recursively find P as median of medians of each sublists.
Step-5: Partition S into S1 and S2 such that S1 contains all elements less than or equal to P and S2 contains all elements greater than P.
Step-6: Now there can be three cases as
a) if |S1| == K, then S1[k] will be the Kth smallest element.
b) if |S1| > K, then Kth element must be present in S1. So discard the second part s2 and recurse on s1 with same algorithm.
c) Otherwise Kth element must be in S2. So discard S1 and recurse on S2 for (K-|S1|)th element in S2.
Подробный код и реализация см. на странице K'th Smallest/Largest Element in Unsorted Array | Набор 3 (линейное время в наихудшем случае)
Анализ сложности: поскольку каждый подсписок содержит 5 элементов, их сортировка займет постоянное количество времени. Таким образом, шаги 2, 3 и 5 можно выполнить за время O(n), а для шага 4 требуется время T(n/5), поскольку мы используем тот же алгоритм рекурсивно для нахождения медианы n/5 медиан. Поскольку мы удаляем не менее n/4 элементов на каждой итерации, в худшем случае после каждой итерации остается 3n/4 элемента. Следовательно, T(n) = T(3n/4) + T(n/5) + O(n).
Let T(n) = a0 + a1*n + a2*(n^2) + …. where a1 != 0.
we have
T(3n/4) = a0 + (3/4)a1*n + (9/16)a2*(n^2) + ….
T(n/5) = a0 + (1/5)a1*n + (1/25)a2*(n^2) + ….
T((3n/4) + (n/5)) = T(19n/20) = a0 + (19/20)a1*n + (361/400)a2*(n^2) + ….
Thus, T(3n/4) + T(n/5) <= a0 + T(19n/20).
Therefore,
T(n) = T(3n/4) + T(n/5) + O(n)
<= T(19n/20) + cn.
Applying the initially obtained formula for general case to this inequality,
we will get T(n) = O(n).
Таким образом, мы имеем наихудший алгоритм линейного времени для решения задачи выбора, основанный на методе удаления и поиска. Точно так же мы можем применять эти типы стратегий для решения линейного программирования с двумя переменными и задач на наименьший охватывающий круг.