Самостоятельная работа №5 По предмету: Алгоритмы проектирования Алгоритмы на языке «разделяй и властвуй»

Пусто()
\(О(1)\)
размер()	\(О(1)\)

Все методы выполняются за время \(O(1)\), поскольку все операции основаны на операции мастеринга.

Стек на основе массива.Одним из удобств массива является возможность в любой момент вернуть элемент массива по индексу. Но если количество элементов в массиве увеличивается, возникает необходимость расширить размер. Массив, который может сам изменять свой размер, называется динамическим массивом.

Амаль	Сложность
Нажмите (значение T)	См. изменение размера().
поп()	\(О(1)\)
заглянуть()	\(О(1)\)
Пусто()	\(О(1)\)
размер()	\(О(1)\)
изменить размер()	Требуется \(O(n)\) в худшем случае и \(O(1)\) в среднем.

Теоретически значение Push(T) равно O(n) наихудшему случаю, но вероятность того, что Resize() будет вызвана, уменьшается после каждого вызова. В результате мы можем принять вышеуказанный метод как имеющий временную сложность.

4. Примеры

Алгоритм сортировки слиянием и принцип его работы
Одним из самых популярных алгоритмов сортировки по методу «разделяй и властвуй» является сортировка слиянием. Алгоритм сортировки слиянием — это алгоритм сортировки несортированных массивов на основе сравнения с полной идеей «разделяй и властвуй» в своем принципе работы.
Итак, алгоритм сортировки слиянием состоит из двух основных частей:

• 
  Рекурсивно разделить заданный массив на две равные части. Этот шаг продолжается до тех пор, пока длина массивов разделов не станет равной 1 (или меньше).
  
• 
  Объедините результирующие массивы обратно и убедитесь, что результирующий массив отсортирован одновременно.
  

Для визуального представления того, как работает алгоритм сортировки слиянием, рассмотрите изображение ниже. Там же показан порядок действий (рис. 6.3).

Рисунок 6.3. Принцип работы алгоритма сортировки слиянием.
Как видите, алгоритм не так сложен для понимания. И если вы еще раз заметили, то левая и правая части массива после первого деления делают то же самое, что и основной массив, то есть проблема части нашей задачи работает так же, как и основная задача.
Шаги алгоритма сортировки слиянием:
1. Функция сортировки слиянием получает массив и его начальную (слева) и конечную точки (справа).
2. Вычисляется середина массива: середина = (левая + правая)/2. Это будет необходимо, чтобы разделить его на две равные части.
3. Сортировка слиянием вызывается рекурсивно для первой и второй частей.
4. Массивы, созданные в частях 2 и 3, объединяются. (См. объединение двух массивов в разделе Массивы)
Алгоритм O (nlogn), намного быстрее, чем простая сортировка пузырьком, вставкой, выбором с O (n²). В целом было показано, что алгоритмы на основе сравнения имеют наибольшую производительность за O(nlogn). Сортировка слиянием является стабильной сортировкой, то есть если в несортированном массиве есть несколько одинаковых элементов, то их порядок не изменится в отсортированном массиве. Для работы алгоритма требуется O(n) дополнительного пространства памяти. Наиболее популярным алгоритмом, основанным на парадигме «разделяй и властвуй», является бинарный поиск. Алгоритм бинарного поиска является одним из наиболее эффективных алгоритмов поиска элемента в отсортированном массиве.