Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 5: Строка 5:
 
Алгоритм '''сортировки слиянием''' (англ. ''merge sort'') является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.
 
Алгоритм '''сортировки слиянием''' (англ. ''merge sort'') является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.
  
'''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math>O(n \log n)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность <math>O(n \log n)</math>
+
'''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math display="inline">\Theta\leftn \log n\right)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность <math>O(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:19, 29 октября 2023

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм сортировки слиянием (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.

Последовательная версия алгоритма сортировки слиянием имеет временную сложность [math]\Theta\leftn \log n\right)[/math] в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует [math]\log n[/math] уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность [math]O(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)