Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты): различия между версиями
Bkmish (обсуждение | вклад) |
Bkmish (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Алгоритм '''сортировки слиянием''' (англ. ''merge sort'') является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи. | Алгоритм '''сортировки слиянием''' (англ. ''merge sort'') является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи. | ||
| − | '''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math display="inline">\Theta(n \log n)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность <math> | + | '''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math display="inline">\Theta(n \log n)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность <math display="inline">\Theta(n \log n)</math> |
'''Параллельная версия''' алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math> | '''Параллельная версия''' алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math> | ||
Версия 22:21, 29 октября 2023
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Алгоритм сортировки слиянием (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.
Последовательная версия алгоритма сортировки слиянием имеет временную сложность [math]\Theta(n \log n)[/math] в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует [math]\log n[/math] уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность [math]\Theta(n \log n)[/math]
Параллельная версия алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности [math]\Theta \left(\frac{n}{(\log n)^2}\right)[/math]
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
2 3 Литература
- Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
- Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (p. 797-805)
