Изменения

Перейти к: навигация, поиск

Упорядоченное множество

3873 байта убрано, 19:25, 4 сентября 2022
м
rollbackEdits.php mass rollback
== Операции над упорядоченным множеством ==
Над упорядоченным множеством <tex>Setset</tex> заданы следующие операции:
* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),
* <tex>\mathrm {delete(set, elem)}</tex> {{---}} удаляет элемент <tex>elem</tex> (сохраняя свойство упорядоченности),
* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает найденный элемент множества <tex>settrue</tex> при наличии элемента в множестве или специальное значение <tex>nullfalse</tex>, если такого элемента нетв противном случае,
* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
== Наивная реализация на массиве ==
Упорядоченное множество <tex>sets</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
Рассмотрим реализацию на примере следующего множества: {0, 2, 4, ..., 5, 3, 1}отсортированного по возрастанию целочисленного массива.
<code>
'''struct''' setSet<T>: '''int''' even <font color=green>// количество четных элементов множества</font color=green> '''int''' odd <font color=green>// количество нечетных элементов множества</font color=green> '''int''' n = even + odd <font color=green>// общее количество элементов множества</font color=green> '''T'''[n] elements <font color=green>// массив элементов множества типа ''T''</font color=green>
</code>
=== '''insert''' ===
<code>
'''func''' insert(setSet<T> s, T elem): s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green> Array.Resize(s.elements, s.n) <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green> '''if''' elem % 2 == 0 <font color=green>// Если элемент elem четный, то,</font color=green> '''int''' i = 0 <font color=green>// ставим счетчик элементов массива на первый элемент,</font color=green> '''while''' elem > s.elements[i] <font color=green>// увеличиваем счетчик до тех пор, пока не найдем первый элемент, больший elem,</font color=green> i = i + 1 '''for''' j = s.n - 1 '''downto''' i+1 <font color=green>// сдвигаем все элементы, большие elem, на единицу вправо,</font color=green> s.elements[j] = s.elements[j - 1] s.elements[i] = elem <font color=green>// вставляем элемент elem в ту ячейку массива, на которую указывает счетчик,</font color=green> s.even = s.even + 1 <font color=green>// увеличиваем количество четных элементов на единицу.</font color=green> Вставляем ''elem'else''' <font color=green>// Если элемент elem нечетный, то,в конец массива</font color=green> '''int''' i = s.even <font color=green>// устанавливаем счетчик на первый нечетный элемент,</font color=green>n - 1 '''while''' elem < s.elements[i] <font color=green>// увеличиваем счетчик до тех пор, пока не найдем первый элемент, меньший elem,</font color=green> i = i + 1 '''for''' j = s.n elements[i - 1 '''downto''' i+1 ] <font color=green>// сдвигаем все элементы, большие elem, на единицу вправоСортируем массив,</font color=green> swap(s.elements[ji] = , s.elements[j i - 1] s.elements[i] = elem ) <font color=green>// вставляем элемент пока ''elem '' не окажется в ту ячейку массива, на которую указывает счетчик,</font color=green> s.odd = s.odd + 1 <font color=green>// увеличиваем количество нечетных элементов на единицунужном месте.</font color=green>
</code>
Время выполнения {{---}} <tex>O(1n)</tex>.
=== '''delete''' ===
<code>
'''func''' delete(setSet<T> s, T elem):
'''int''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green>
'''while''' elem != i < s.n '''and''' s.elements[i] && i < s.n != elem <font color=green>// Ищем элемент индекс элемента ''elem''.</font color=green> i = i + 1+
'''if''' i != s.n <font color=green>// Если элемент найден, то</font color=green>
'''for''' j = i '''to''' s.n - 2 <font color=green>// сдвигаем все элементы массива, следующие за текущимбольшие ''elem'', на единицу влево</font color=green> s.elements[j] = s.elements[j + 1] <font color=green>// на одну позицию влево (тем самым удаляем элемент elem; последний элемент массива дублируетсяудаляется).</font color=green> '''if''' elem % 2 == 0 <font color=green>// Если удаленный элемент был четным, то</font color=green> s.even = s.even - 1 <font color=green>// уменьшаем количество четных элементов на единицу,</font color=green> '''else''' <font color=green>// в противном случае</font color=green> s.odd = s.odd - 1 <font color=green>// уменьшаем количество нечетных элементов.</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем общее число элементов массива на единицу.</font color=green> Array.Resize(s.elements, s.n) <font color=green>// Удаляем дубликат последнего элемента.</font color=green>
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
=== '''search''' ===
Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].
 
<code>
'''Tbool''' search(setSet<T> s, T elem): int i '''forint''' i = 0 '''to''' s.n - 1 '''if''' binSearch(s.elements[i] == , elem <font color=green>// Если элемент elem существует,</font color=green>) '''return''' s.elements[i] <font color=green>// то выводим его,</font color=green> '''return''' ''null'' elem <font color=green>// в противном случае возвращаем ''null''Сравниваем найденное значение с искомым...</font color=green>
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
=== '''minimum''' ===
Первый элемент множества минимальный, так как массив отсортирован по возрастанию.
=== '''minimum''' ===
<code>
'''T''' minimum(setSet<T> s): '''T''' min = s.elements[0] <font color=green>// Принимаем первый элемент множества за минимальный.</font color=green> '''int''' i '''for''' i = 1 '''to''' s.n - 1 '''if''' min > s.elements[i] <font color=green>// Ищем минимальный элемент множества</font color=green> min = s.elements[i] '''return''' min <font color=green>// и выводим его.</font color=green>
</code>
Время выполнения {{---}} <tex>O(n1)</tex>. 
=== '''maximum''' ===
Выполняется аналогично операции <codetex> '''T''' maximum\mathrm {minimum(set<T> s): '''T''' max = s.elements[0] <font color=green>// Принимаем первый элемент множества за максимальный.</font color=green> '''int''' i '''for''' i = 1 '''to''' s.n - 1 '''if''' max < s.elements[i] <font color=green>// Ищем максимальный элемент множества</font color=green> max = s.elements[i] '''return''' max <font color=green>// и выводим его.</font color=green></code>Время выполнения {{---}} <tex>O(n)</tex>.
 
=== '''predecessor''' ===
<code>
'''T''' predecessormaximum(setSet<T> s, T elem): '''int''' i '''for''' i = 1 '''to''' s.n - 1 'T''if''' elem =max = s.elements[i] <font color=green>// Если в массиве находим елемент elem,</font color=green> '''return''' s.elements[i n - 1] <font color=green>// то выводим предшествующий ему элемент.</font color=green> '''return''' ''null'' <font color=green>// Иначе выводим ''null''.</font color=green>max
</code>
Время выполнения {{---}} <tex>O(n1)</tex>.
=== '''successor''' ===
В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.
=== '''successor''' ===
<code>
'''T''' successor(setSet<T> s, T elem): '''int''' i '''for''' i = 1 '''toif''' elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального,</font color=green> '''ifreturn''' ''null'' elem == s.elements[i] <font color=green>// Если в массиве находим елемент elem,возвращаем ''null''.</font color=green> '''returnelse if''' elem < s.elements[i + 10] '''return''' min(s) <font color=green>// то выводим следующий за ним Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''returnint''' ''null'' i = binSearch(s.elements, elem) <font color=green>// Иначе выводим ищем элемент, больший ''nullelem''.</font color=green> '''return''' s.elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==
* множество натуральных чисел <tex> \mathbb N </tex>,
* множество целых чисел <tex> \mathbb Z </tex>,
* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке порядке]].
== Источники информации ==
* Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
* Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.
* [http://ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество — Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория: Структуры данных]]
1632
правки

Навигация