Бинарные операции над упорядоченными множествами

Бинарные операции над упорядоченными множествами

436
ПОДЕЛИТЬСЯ

В данной статье мы разглядим методы с наименьшей трудности реализации для упорядоченных множеств. В предшествующей статье я писал о бинарных операций на неупорядоченные наборы.

Ассоциация упорядоченных множеств
IV. пересечении упорядоченных множеств
II. Симметрическая разность упорядоченных множеств
Вывод Содержание
I. Разница меж упорядоченных множеств
III.
пересечении упорядоченных множеств
Пересечение 2-ух упорядоченных множеств A и B — это множество тех частей A и B, которые сразу относятся к обоим наборам, без дубликатов. I. Сложность метода — O(m+n), где m и n — длины входных множеств A и B , соответственно.
Сделал маленькую анимацию, чтоб показать, как работает метод.

Пример реализации в javascript:
функция intersec_sort_arr(array_1,array_2)
{
var n = array_1.длина, m = array_2.длина, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не достигнут конец массива
{
раз (array_1[i] == array_2[j])
{
array_3[k] = array_1[i]; // запись элемента в массиве array_3
k++,i++,j++; // и перемещения всех 3-х массивов
} else {
раз (array_1[i] < array_2[j]) {
i++; // перейти на должность первого массива
} else {
j++; // перейти на позиции второго массива
}
}
}
возвращение array_3;
}
Обращение к функции:
intersec_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // выход [3, 8]
Сложность метода — O(m+n), где m и n — длина входной упорядоченных множеств A и B , соответственно. Разница меж упорядоченных множеств
Разница меж 2-мя упорядоченными множествами A и B — это множество частей A, не совпадают с элементами B, без дубликатов. II.

функция diff_sort_arr(array_1,array_2)
{
var n = array_1.длина, m = array_2.длина, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не достигнут конец массива
{
раз (array_1[i] == array_2[j])
{
i++,j++;
} else {
раз (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // перейти на должность первого массива
} else {
j++; // перейти на позиции второго массива
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
}
возвращение array_3;
}
diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // выход [1, 2, 5]
Ассоциация упорядоченных множеств
Объединение 2-ух упорядоченных множеств A и B — это набор с элементами A и элементами множества B, без дубликатов. Сложность метода — O(m+n), где m и n — длина входной упорядоченных множеств A и B , соответственно. III.

функция sum_sort_arr(array_1,array_2)
{
var n = array_1.длина, m = array_2.длина, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не достигнут конец массива
{
раз (array_1[i] == array_2[j])
{
array_3[k] = array_1[i];
k++,i++,j++;
} else {
раз (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // перейти на должность первого массива
} else {
array_3[k] = array_2[j];
k++;
j++; // перейти на позиции второго массива
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
} else {
if (j < m)
{
while (j < m) {
array_3[k] = array_2[j];
k++, j++;
}
}
}
возвращение array_3;
}
sum_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // выход[1, 2, 3, 5, 6, 8, 12, 24, 47]
Сложность метода составляет O(2(m+n)), где m и n — длина входной упорядоченных множеств A и B , соответственно. IV. Симметрическая разность упорядоченных множеств
Симметрическая разность 2-ух упорядоченных множеств A и B является множество, в которое входят все элементы первого упорядоченного множества, которые не входят во 2-ой упорядоченного множества, а также те элементы второго упорядоченного множества, которые не входят в 1-ый упорядоченный набор.
На самом деле это вычитание множеств, 1-ый A от B, то B из A.
функция symmetric_diff_sort_arr(array_1,array_2)
{
var n = array_1.длина, m = array_2.длина, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не достигнут конец массива
{
раз (array_1[i] == array_2[j])
{
i++,j++;
} else {
раз (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // перейти на должность первого массива
} else {
j++; // перейти на позиции второго массива
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
}

n = array_2.длина, m = array_1.длина, j = 0, i = 0;
while ((i < n) && (j < m)) // пока не достигнут конец массива
{
раз (array_2[i] == array_1[j])
{
i++,j++;
} else {
раз (array_2[i] < array_1[j]) {
array_3[k] = array_2[i];
k++;
i++; // перейти на должность первого массива
} else {
j++; // перейти на позиции второго массива
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_2[i];
k++, i++;
}
}

возвращение array_3;
}
symmetric_diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // выход[1, 2, 5, 6, 12, 24, 47]
Употреблял способ, описанный в моей предшествующей статье, обработки массива был чрезвычайно медленным. Вывод
Я нередко работаю с отсортированные массивы, потому эти методы существенно убыстрить процесс. Пример реализации способа intersec_sort_arr, вы сможете узреть в моем приложения для vk.com. Используя этот способ, я отыскать общих членов общества, работающих с отсортированные массивы, в миллионы частей, способ справляется чрезвычайно быстро. habrahabr.ru