Упорядоченное множество: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Добавлены алгоритмы |
DmitTrix (обсуждение | вклад) отмена: 1) этому не место на стр. значений 2) частные случаи, неясна значимость и авторитетность |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 5: | Строка 5: | ||
{{неоднозначность}} |
{{неоднозначность}} |
||
== Бинарные операции над упорядоченными множествами == |
|||
=== Пересечение упорядоченных множеств === |
|||
Сложность алгоритма '''O(m+n)''', где '''m''' и '''n''' — длины входных множеств '''A''' и '''B''' соответственно. |
|||
Пример кода на языке программирования Javascript: |
|||
<source lang="javascript"> |
|||
function intersec_sort_arr(array_1,array_2) |
|||
{ |
|||
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; |
|||
while ((i < n) && (j < m)) // пока не дошли до конца массива |
|||
{ |
|||
if (array_1[i] == array_2[j]) |
|||
{ |
|||
array_3[k] = array_1[i]; // запишем элемент в массив array_3 |
|||
k++,i++,j++; // и сдвинем позицию во всех 3 массивах |
|||
} else { |
|||
if (array_1[i] < array_2[j]) { |
|||
i++; // сдвинем позицию в первом массиве |
|||
} else { |
|||
j++; // сдвинем позицию во втором массиве |
|||
} |
|||
} |
|||
} |
|||
return array_3; |
|||
} |
|||
</source> |
|||
=== Разность упорядоченных множеств === |
|||
Сложность алгоритма '''O(m+n)''', где '''m''' и '''n''' — длины входных множеств '''A''' и '''B''' соответственно. |
|||
Пример кода на языке программирования Javascript: |
|||
<source lang="javascript"> |
|||
function diff_sort_arr(array_1,array_2) |
|||
{ |
|||
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; |
|||
while ((i < n) && (j < m)) // пока не дошли до конца массива |
|||
{ |
|||
if (array_1[i] == array_2[j]) |
|||
{ |
|||
i++,j++; |
|||
} else { |
|||
if (array_1[i] < array_2[j]) { |
|||
array_3[k] = array_1[i]; |
|||
k++; |
|||
i++; // сдвинем позицию в первом массиве |
|||
} else { |
|||
j++; // сдвинем позицию во втором массиве |
|||
} |
|||
} |
|||
} |
|||
while (i < n) { |
|||
array_3[k] = array_1[i]; |
|||
k++, i++; |
|||
} |
|||
return array_3; |
|||
} |
|||
</source> |
|||
=== Объединение упорядоченных множеств === |
|||
Сложность алгоритма '''O(m+n)''', где '''m''' и '''n''' — длины входных множеств '''A''' и '''B''' соответственно. |
|||
Пример кода на языке программирования Javascript: |
|||
<source lang="javascript"> |
|||
function sum_sort_arr(array_1,array_2) |
|||
{ |
|||
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; |
|||
while ((i < n) && (j < m)) // пока не дошли до конца массива |
|||
{ |
|||
if (array_1[i] == array_2[j]) |
|||
{ |
|||
array_3[k] = array_1[i]; |
|||
k++,i++,j++; |
|||
} else { |
|||
if (array_1[i] < array_2[j]) { |
|||
array_3[k] = array_1[i]; |
|||
k++; |
|||
i++; // сдвинем позицию в первом массиве |
|||
} else { |
|||
array_3[k] = array_2[j]; |
|||
k++; |
|||
j++; // сдвинем позицию во втором массиве |
|||
} |
|||
} |
|||
} |
|||
while (i < n) { |
|||
array_3[k] = array_1[i]; |
|||
k++, i++; |
|||
} |
|||
while (j < m) { |
|||
array_3[k] = array_2[j]; |
|||
k++, j++; |
|||
} |
|||
return array_3; |
|||
} |
|||
</source> |
|||
=== <nowiki/> === |
|||
Текущая версия от 13:50, 11 февраля 2015
Упорядоченное множество — множество с заданным отношением порядка.
Примечания
Если вы попали сюда из другой статьи Википедии, пожалуйста, вернитесь и уточните ссылку так, чтобы она указывала на нужную статью.