Пространство имён страницы (page_namespace) | 0 |
Название страницы (без пространства имён) (page_title) | 'Упорядоченное множество' |
Полное название страницы (page_prefixedtitle) | 'Упорядоченное множество' |
Последние десять редакторов страницы (page_recent_contributors) | [
0 => '94.181.76.176',
1 => 'Addbot',
2 => 'HRoestBot',
3 => 'Koterpillar',
4 => 'DmitTrix'
] |
Вики-текст старой страницы до правки (old_wikitext) | ''''Упорядоченное множество''' — [[множество]] с заданным [[отношение порядка|отношением порядка]].
* [[Частично упорядоченное множество]]
* [[Линейно упорядоченное множество]]
* [[Вполне упорядоченное множество]]
{{неоднозначность}}
== Бинарные операции над упорядоченными множествами ==
=== Пересечение упорядоченных множеств ===
Сложность алгоритма '''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/> ===' |
Вики-текст новой страницы после правки (new_wikitext) | ''''Упорядоченное множество''' — [[множество]] с заданным [[отношение порядка|отношением порядка]].
* [[Частично упорядоченное множество]]
* [[Линейно упорядоченное множество]]
* [[Вполне упорядоченное множество]]
{{неоднозначность}}
== Бинарные операции над упорядоченными множествами ==
=== Пересечение упорядоченных множеств ===
Сложность алгоритма '''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/> ==
* Бинарные операции над упорядоченными множествами - Роман Мещеряков [Интернет ресурс - http://habrahabr.ru/post/250191/]' |