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

Материал из Викиконспекты
Версия от 00:57, 1 июля 2015; 176.59.1.236 (обсуждение) (successor)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Упорядоченное множество (англ. 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 с.
  • Википедия — Упорядоченное множество