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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Наивная реализация на массиве)
м (rollbackEdits.php mass rollback)
 
(не показаны 32 промежуточные версии 3 участников)
Строка 7: Строка 7:
 
* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</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 {delete(set, elem)}</tex> {{---}} удаляет элемент <tex>elem</tex> (сохраняя свойство упорядоченности),
* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает найденный элемент множества <tex>set</tex> или специальное значение <tex>null</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 {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,
 
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
 
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
Строка 14: Строка 14:
  
 
== Наивная реализация на массиве ==
 
== Наивная реализация на массиве ==
Упорядоченное множество <tex>set</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[0..n-1]</tex>.
+
Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
  
Рассмотрим реализацию на примере отсортированного по неубыванию массива.
+
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
  
 
<code>
 
<code>
 
  '''struct''' Set<T>:
 
  '''struct''' Set<T>:
 
   '''int''' n                            <font color=green>// количество элементов множества</font color=green>
 
   '''int''' n                            <font color=green>// количество элементов множества</font color=green>
   '''T'''[n] elements                    <font color=green>// массив элементов множества типа T</font color=green>
+
   '''T'''[n] elements                    <font color=green>// массив элементов множества типа ''T''</font color=green>
 
</code>
 
</code>
  
Строка 27: Строка 27:
 
<code>
 
<code>
 
  '''func''' insert(Set<T> s, T elem):
 
  '''func''' insert(Set<T> s, T elem):
     s.n = s.n + 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>
+
                                                      <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green>
     '''if''' elem % 2 == 0                              <font color=green>// Если элемент elem четный, то,</font color=green>
+
     s.elements[s.n - 1] = elem                      <font color=green>// Вставляем ''elem'' в конец массива</font color=green>
        '''int''' i = 0                                <font color=green>// ставим счетчик элементов массива на первый элемент,</font color=green>
+
    '''int''' i = s.n - 1
        '''while''' elem > s.elements[i]                <font color=green>// увеличиваем счетчик до тех пор, пока не найдем первый элемент, больший elem,</font color=green>
+
    '''while''' s.elements[i] < s.elements[i - 1]          <font color=green>// Сортируем массив,</font color=green>
            i = i + 1
+
        swap(s.elements[i], s.elements[i - 1])      <font color=green>// пока ''elem'' не окажется в нужном месте.</font color=green>
        '''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>
 
    '''else'''                                          <font color=green>// Если элемент elem нечетный, то,</font color=green>
 
        '''int''' i = s.even                            <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.odd = s.odd + 1                        <font color=green>// увеличиваем количество нечетных элементов на единицу.</font color=green>
 
 
</code>
 
</code>
 
Время выполнения {{---}} <tex>O(n)</tex>.
 
Время выполнения {{---}} <tex>O(n)</tex>.
Строка 52: Строка 40:
 
  '''func''' delete(Set<T> s, T elem):
 
  '''func''' delete(Set<T> s, T elem):
 
     '''int''' i = 0                                        <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green>
 
     '''int''' i = 0                                        <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green>
     '''while''' elem != s.elements[i] && i < s.n            <font color=green>// Ищем элемент elem.</font color=green>
+
     '''while''' i < s.n '''and''' s.elements[i] != elem          <font color=green>// Ищем индекс элемента ''elem''.</font color=green>
         i = i + 1
+
         i++
 
     '''if''' i != s.n                                      <font color=green>// Если элемент найден, то</font color=green>
 
     '''if''' i != s.n                                      <font color=green>// Если элемент найден, то</font color=green>
         '''for''' j = i '''to''' s.n - 2                          <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.elements[j] = s.elements[j + 1]        <font color=green>// на одну позицию влево (elem удаляется).</font color=green>
        '''if''' elem % 2 == 0                              <font color=green>// Если удаленный элемент был четным, то</font color=green>
+
         s.n = s.n - 1                                <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>
 
</code>
 
Время выполнения {{---}} <tex>O(n)</tex>.
 
Время выполнения {{---}} <tex>O(n)</tex>.
  
 
=== '''search''' ===
 
=== '''search''' ===
 +
Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].
 +
 
<code>
 
<code>
  '''T''' search(Set<T> s, T elem):
+
  '''bool''' search(Set<T> s, T elem):
    int i
+
     '''int''' i = binSearch(s.elements, elem)
     '''for''' i = 0 '''to''' s.n - 1
+
    '''return''' s.elements[i] == elem                        <font color=green>// Сравниваем найденное значение с искомым...</font color=green>
        '''if''' s.elements[i] == elem               <font color=green>// Если элемент elem существует,</font color=green>
 
            '''return''' s.elements[i]               <font color=green>// то выводим его,</font color=green>
 
    '''return''' ''null''                                <font color=green>// в противном случае возвращаем ''null''.</font color=green>
 
 
</code>
 
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
+
Время выполнения {{---}} <tex>O(\log n)</tex>.
  
 +
=== '''minimum''' ===
 +
Первый элемент множества минимальный, так как массив отсортирован по возрастанию.
  
=== '''minimum''' ===
 
 
<code>
 
<code>
 
  '''T''' minimum(Set<T> s):
 
  '''T''' minimum(Set<T> s):
     '''T''' min = s.elements[0]              <font color=green>// Принимаем первый элемент множества за минимальный.</font color=green>
+
     '''T''' min = s.elements[0]
    '''int''' i
+
     '''return''' min
    '''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>
 
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
+
Время выполнения {{---}} <tex>O(1)</tex>.
  
 +
=== '''maximum''' ===
 +
Выполняется аналогично операции <tex>\mathrm {minimum(set)}</tex>.
  
=== '''maximum''' ===
 
 
<code>
 
<code>
 
  '''T''' maximum(Set<T> s):
 
  '''T''' maximum(Set<T> s):
     '''T''' max = s.elements[0]              <font color=green>// Принимаем первый элемент множества за максимальный.</font color=green>
+
     '''T''' max = s.elements[s.n - 1]
    '''int''' i
+
     '''return''' max
    '''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>
 
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
+
Время выполнения {{---}} <tex>O(1)</tex>.
  
 +
=== '''successor''' ===
 +
В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.
  
=== '''predecessor''' ===
 
<code>
 
'''T''' predecessor(Set<T> s, T elem):
 
    '''int''' i
 
    '''for''' i = 1 '''to''' s.n - 1
 
        '''if''' elem == s.elements[i]        <font color=green>// Если в массиве находим елемент elem,</font color=green>
 
            '''return''' s.elements[i - 1]    <font color=green>// то выводим предшествующий ему элемент.</font color=green>
 
    '''return''' ''null''                          <font color=green>// Иначе выводим ''null''.</font color=green>
 
</code>
 
Время выполнения {{---}} <tex>O(n)</tex>.
 
 
 
=== '''successor''' ===
 
 
<code>
 
<code>
 
  '''T''' successor(Set<T> s, T elem):
 
  '''T''' successor(Set<T> s, T elem):
     '''int''' i
+
     '''if''' elem > s.elements[s.n - 1]                            <font color=green>// Если элемент больше максимального,</font color=green>
    '''for''' i = 1 '''to''' s.n - 1
+
         '''return''' ''null''                                         <font color=green>// возвращаем ''null''.</font color=green>
         '''if''' elem == s.elements[i]        <font color=green>// Если в массиве находим елемент elem,</font color=green>
+
    '''else if''' elem < s.elements[0]
            '''return''' s.elements[i + 1]     <font color=green>// то выводим следующий за ним элемент.</font color=green>
+
        '''return''' min(s)                                        <font color=green>// Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green>
     '''return''' ''null''                          <font color=green>// Иначе выводим ''null''.</font color=green>
+
     '''int''' i = binSearch(s.elements, elem)                      <font color=green>// Иначе ищем элемент, больший ''elem''.</font color=green>
 +
    '''return''' s.elements[i]
 
</code>
 
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
+
Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
 
 
  
В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
+
== Замечания ==
 +
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
  
 
== Примеры ==  
 
== Примеры ==  
Строка 134: Строка 100:
 
* множество натуральных чисел <tex>  \mathbb N </tex>,
 
* множество натуральных чисел <tex>  \mathbb N </tex>,
 
* множество целых чисел  <tex>  \mathbb Z </tex>,
 
* множество целых чисел  <tex>  \mathbb Z </tex>,
* строки, отсортированные в лексикографическом порядке.
+
* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке]].
  
 
== Источники информации ==
 
== Источники информации ==

Текущая версия на 19:25, 4 сентября 2022

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