Изменения
Нет описания правки
{{Определение|definition== Многопоточная сортировка слиянием ==Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' (англ. ''chromatic polynomial''). Обозначение: <tex>P(G,x)</tex>.}}
===Алгоритм с многопоточным слияниемХроматический многочлен простой цепи ===Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов Пусть <mathtex>T[left1 \dots right1]T_n</mathtex> и — простая цепь, состоящая из <mathtex>T[left2 \dots right2]n</mathtex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в массив один из <mathtex>A[left3 \dots right3]x</mathtex>:# Убедимсяцветов, что размер <math>T[left1 \dots right1]</math> больше либо равен размеру <math>T[left2 \dots right2]</math># Найдем вторую и последующие в один из <mathtex>x = T[mid1]- 1</mathtex> - середину первого массива цветов (<math>x</math> также является и медианой этого массиват.е. так, чтобы цвет не совпадал с предыдущей вершиной)# При помощи бинарного поиска найдем . Тогда <mathtex>mid2</math> такоеP(T_n, что <math>\forall y \in T[left2 \dots mid2 - 1]: y < x</math># <math>mid3 ) = left3 + (mid1 - left1) + x(mid2 - left2)</math># <math>A[mid3] = x</math># Сольем <math>T[right1 \dots mid1 - 1]</math> и <math>T[rigth2 \dots mid2]</math> в <math>A[right3 \dots mid3 ) ^ {n - 1]}</mathtex># Сольем <math>T[mid1 + 1 \dots right1]</math> и <math>T[mid2 \dots right2]</math> в <math>A[mid3 + 1 \dots right3]</math>Приведем псевдокод данного алгоритма:.
