Упорядоченное множество — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(successor)
 
(не показано 56 промежуточных версий 5 участников)
Строка 1: Строка 1:
==Определение==
+
'''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является [[отношение порядка|отношением порядка]].
'''Упорядоченное множество''' представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве.
 
  
==Операции над упорядоченным множеством==
+
'''Вполне упорядоченным множеством''', которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент.
Над упорядоченным множеством <tex>Set</tex> заданы следующие операции:
 
  
=== Search ===
+
== Операции над упорядоченным множеством ==
Функция '''Search(Set, key)''', которая получает на вход искомый ключ <tex>key</tex>, и возвращает указатель на элемент множества <tex>Set</tex> или специальное значение <tex>null</tex>, если такого элемента нет.
+
Над упорядоченным множеством <tex>set</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>true</tex> при наличии элемента в множестве или <tex>false</tex> в противном случае,
 +
* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,
 +
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
 +
* <tex>\mathrm {predecessor(set, elem)}</tex> {{---}} возвращает элемент, стоящий перед элементом <tex>elem</tex> множества <tex>set</tex>.
 +
* <tex>\mathrm {successor(set, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>.
  
=== Minimum ===
+
== Наивная реализация на массиве ==
Функция '''Minimum(Set)''' возвращает указатель на минимальный элемент множества <tex>Set</tex>.
+
Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
  
=== Maximum ===
+
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
Функция '''Maximum(Set)''' возвращает указатель на максимальный элемент множества <tex>Set</tex>.
 
  
=== Predecessor ===
+
<code>
Функция '''Predecessor(Set, elem)''' возвращает указатель на элемент, стоящий перед элементом <tex>elem</tex> множества <tex>Set</tex>.
+
'''struct''' Set<T>:
 +
  '''int''' n                            <font color=green>// количество элементов множества</font color=green>
 +
  '''T'''[n] elements                    <font color=green>// массив элементов множества типа ''T''</font color=green>
 +
</code>
  
=== Successor ===
+
=== '''insert''' ===
Функция '''Successor(Set, elem)''' возвращает указатель на элемент, стоящий после элемента <tex>elem</tex> множества <tex>Set</tex>.
+
<code>
 +
'''func''' insert(Set<T> s, T elem):
 +
    s.n = s.n + 1                                    <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green>
 +
                                                      <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green>
 +
    s.elements[s.n - 1] = elem                      <font color=green>// Вставляем ''elem'' в конец массива</font color=green>
 +
    '''int''' i = s.n - 1
 +
    '''while''' s.elements[i] < s.elements[i - 1]          <font color=green>// Сортируем массив,</font color=green>
 +
        swap(s.elements[i], s.elements[i - 1])      <font color=green>// пока ''elem'' не окажется в нужном месте.</font color=green>
 +
</code>
 +
Время выполнения {{---}} <tex>O(n)</tex>.
  
=== Insert ===
+
=== '''delete''' ===
Функция '''Insert(Set, elem, elemKey)''' добавляет заданный элемент <tex>elem</tex>, имеющий ключ <tex>elemKey</tex>, в подходящее место множества <tex>Set</tex> (сохраняя свойство упорядоченности).
+
<code>
 +
'''func''' delete(Set<T> s, T elem):
 +
    '''int''' i = 0                                        <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green>
 +
    '''while''' i < s.n '''and''' s.elements[i] != elem          <font color=green>// Ищем индекс элемента ''elem''.</font color=green>
 +
        i++
 +
    '''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>
 +
        s.n = s.n - 1                                <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green>
 +
</code>
 +
Время выполнения {{---}} <tex>O(n)</tex>.
  
=== Delete ===
+
=== '''search''' ===
Функция '''Delete(Set, key)''' удаляет элемент, имеющий ключ <tex>key</tex> (сохраняя свойство упорядоченности).
+
Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].
  
==Пример упорядоченного множества:==  
+
<code>
Примерами упорядоченных множеств могут служить такие структуры как деревья.
+
'''bool''' search(Set<T> s, T elem):
 +
    '''int''' i = binSearch(s.elements, elem)
 +
    '''return''' s.elements[i] == elem                        <font color=green>// Сравниваем найденное значение с искомым...</font color=green>
 +
</code>
 +
Время выполнения {{---}} <tex>O(\log n)</tex>.
  
== Литература ==
+
=== '''minimum''' ===
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
+
Первый элемент множества минимальный, так как массив отсортирован по возрастанию.
 +
 
 +
<code>
 +
'''T''' minimum(Set<T> s):
 +
    '''T''' min = s.elements[0]
 +
    '''return''' min
 +
</code>
 +
Время выполнения {{---}} <tex>O(1)</tex>.
 +
 
 +
=== '''maximum''' ===
 +
Выполняется аналогично операции <tex>\mathrm {minimum(set)}</tex>.
 +
 
 +
<code>
 +
'''T''' maximum(Set<T> s):
 +
    '''T''' max = s.elements[s.n - 1]
 +
    '''return''' max
 +
</code>
 +
Время выполнения {{---}} <tex>O(1)</tex>.
 +
 
 +
=== '''successor''' ===
 +
В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.
 +
 
 +
<code>
 +
'''T''' successor(Set<T> s, T elem):
 +
    '''if''' elem > s.elements[s.n - 1]                            <font color=green>// Если элемент больше максимального,</font color=green>
 +
        '''return''' ''null''                                          <font color=green>// возвращаем ''null''.</font color=green>
 +
    '''else if''' elem < s.elements[0]
 +
        '''return''' min(s)                                        <font color=green>// Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green>
 +
    '''int''' i = binSearch(s.elements, elem)                      <font color=green>// Иначе ищем элемент, больший ''elem''.</font color=green>
 +
    '''return''' s.elements[i]
 +
</code>
 +
Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
 +
 
 +
== Замечания ==
 +
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
 +
 
 +
== Примеры ==
 +
* Пустое множество <tex>  \varnothing </tex>,
 +
* множество натуральных чисел <tex>  \mathbb N </tex>,
 +
* множество целых чисел  <tex>  \mathbb Z </tex>,
 +
* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке]].
 +
 
 +
== Источники информации ==
 +
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
 +
* Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
 +
* Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.
 +
* [http://ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория:Деревья поиска]]
 +
[[Категория: Структуры данных]]

Текущая версия на 00:57, 1 июля 2015

Упорядоченное множество (англ. ordered set) представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является отношением порядка.

Вполне упорядоченным множеством, которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент.

Операции над упорядоченным множеством[править]

Над упорядоченным множеством [math]set[/math] заданы следующие операции:

  • [math]\mathrm {insert(set, elem)}[/math] — добавляет заданный элемент [math]elem[/math] в подходящее место множества [math]set[/math] (сохраняя свойство упорядоченности),
  • [math]\mathrm {delete(set, elem)}[/math] — удаляет элемент [math]elem[/math] (сохраняя свойство упорядоченности),
  • [math]\mathrm {search(set, elem)}[/math] — получает на вход искомое значение элемента [math]elem[/math] и возвращает [math]true[/math] при наличии элемента в множестве или [math]false[/math] в противном случае,
  • [math]\mathrm {minimum(set)}[/math] — возвращает минимальный элемент множества [math]set[/math],
  • [math]\mathrm {maximum(set)}[/math] — возвращает максимальный элемент множества [math]set[/math],
  • [math]\mathrm {predecessor(set, elem)}[/math] — возвращает элемент, стоящий перед элементом [math]elem[/math] множества [math]set[/math].
  • [math]\mathrm {successor(set, elem)}[/math] — возвращает элемент, стоящий после элемента [math]elem[/math] множества [math]set[/math].

Наивная реализация на массиве[править]

Упорядоченное множество [math]s[/math], содержащее [math]n[/math] элементов, можно реализовать с помощью отсортированного массива [math]elements[0..n-1][/math].

Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.

struct Set<T>:
  int n                            // количество элементов множества
  T[n] elements                    // массив элементов множества типа T

insert[править]

func insert(Set<T> s, T elem):
    s.n = s.n + 1                                    // Увеличиваем количество элементов множества на единицу,
                                                     // увеличиваем размер массива с элементами множества на единицу.
    s.elements[s.n - 1] = elem                       // Вставляем elem в конец массива
    int i = s.n - 1
    while s.elements[i] < s.elements[i - 1]          // Сортируем массив,
        swap(s.elements[i], s.elements[i - 1])       // пока elem не окажется в нужном месте.

Время выполнения — [math]O(n)[/math].

delete[править]

func delete(Set<T> s, T elem):
    int i = 0                                         // Устанавливаем счетчик на первый элемент.
    while i < s.n and s.elements[i] != elem           // Ищем индекс элемента elem.
        i++
    if i != s.n                                       // Если элемент найден, то
        for j = i to s.n - 2                          // сдвигаем все элементы массива, большие elem,
            s.elements[j] = s.elements[j + 1]         // на одну позицию влево (elem удаляется).
        s.n = s.n - 1                                 // Уменьшаем число элементов массива на единицу.

Время выполнения — [math]O(n)[/math].

search[править]

Для нахождения результата используем бинарный поиск.

bool search(Set<T> s, T elem):
    int i = binSearch(s.elements, elem)
    return s.elements[i] == elem                         // Сравниваем найденное значение с искомым...

Время выполнения — [math]O(\log n)[/math].

minimum[править]

Первый элемент множества минимальный, так как массив отсортирован по возрастанию.

T minimum(Set<T> s):
    T min = s.elements[0]
    return min

Время выполнения — [math]O(1)[/math].

maximum[править]

Выполняется аналогично операции [math]\mathrm {minimum(set)}[/math].

T maximum(Set<T> s):
    T max = s.elements[s.n - 1]
    return max

Время выполнения — [math]O(1)[/math].

successor[править]

В операции используется правосторонний бинарный поиск, который вернет такое [math]i[/math], что [math] s.elements[i - 1]\leqslant elem \lt s.elements[i] [/math].

T successor(Set<T> s, T elem):
    if elem > s.elements[s.n - 1]                            // Если элемент больше максимального,
        return null                                          // возвращаем null.
    else if elem < s.elements[0]
        return min(s)                                        // Если элемент меньше минимального, возвращаем минимальный элемент.
    int i = binSearch(s.elements, elem)                      // Иначе ищем элемент, больший elem.
    return s.elements[i]

Время выполнения — [math]O(\log n)[/math]. Операция [math]\mathrm{predecessor}[/math] выполняется аналогичным образом.

Замечания[править]

  • В случае, когда упорядоченность элементов коллекции не важна, возможно использование хешей.

Примеры[править]

  • Пустое множество [math] \varnothing [/math],
  • множество натуральных чисел [math] \mathbb N [/math],
  • множество целых чисел [math] \mathbb Z [/math],
  • строки, отсортированные в лексикографическом порядке.

Источники информации[править]

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
  • Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
  • Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.
  • Википедия — Упорядоченное множество