Упорядоченное множество - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:40Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:55, 1 сентября 2022

2022-09-01T04:55:38Z

176.59.1.236: /* successor */

2015-06-30T21:57:09Z

‎successor

188.162.65.27: /* successor */

2015-06-30T21:53:38Z

‎successor

188.162.65.27: /* Наивная реализация на массиве */

2015-06-30T21:52:48Z

‎Наивная реализация на массиве

176.59.1.236: /* Замечания */

2015-06-30T21:51:10Z

‎Замечания

176.59.1.236: /* successor */

2015-06-30T21:46:50Z

‎successor

188.162.65.27: /* search */

2015-06-30T20:50:49Z

‎search

188.162.65.27: /* Наивная реализация на массиве */

2015-06-30T20:50:01Z

‎Наивная реализация на массиве

176.59.1.236 в 20:47, 30 июня 2015

2015-06-30T20:47:38Z

← Предыдущая		Версия 16:25, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является [[отношение порядка\|отношением порядка]].		'''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является [[отношение порядка\|отношением порядка]].

← Предыдущая		Версия 04:55, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является [[отношение порядка\|отношением порядка]].		'''Упорядоченное множество''' (англ. ''ordered set'') представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является [[отношение порядка\|отношением порядка]].

@@ Строка 80: / Строка 80: @@
 === '''successor''' ===
-В операции используется [[Целочисленный двоичный поиск|левосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.
+В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.
 <code>

@@ Строка 86: / Строка 86: @@
       '''if''' elem > s.elements[s.n - 1]                            <font color=green>// Если элемент больше максимального,</font color=green>
           '''return''' ''null''                                          <font color=green>// возвращаем ''null''.</font color=green>
-      '''else if'''
+      '''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>

@@ Строка 78: / Строка 78: @@
 </code>
 Время выполнения {{---}} <tex>O(1)</tex>.
 === '''successor''' ===
-В операции используется [[Целочисленный двоичный поиск|левосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex> s.elements[i - 1]<elem\leqslant s.elements[i] </tex>.
+В операции используется [[Целочисленный двоичный поиск|левосторонний бинарный поиск]], который вернет такое <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'''
+      '''else if'''
-          '''if''' elem < s.elements[0]                              <font color=green>// Если элемент меньше минимального,</font color=green>
+          '''return''' min(s)                                        <font color=green>// Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green>
-             i = 0                                            <font color=green>// возвращаем минимальный элемент.</font color=green>
+     '''int''' i = binSearch(s.elements, elem)                      <font color=green>// Иначе ищем элемент, больший ''elem''.</font color=green>
-         '''else'''
+     '''return''' s.elements[i]
 </code>
-Время выполнения {{---}} <tex>O(\log n)</tex>.
+Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
 == Замечания ==

@@ Строка 114: / Строка 114: @@
 == Замечания ==
 * В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
 == Примеры ==

@@ Строка 55: / Строка 55: @@
   '''bool''' search(Set<T> s, T elem):
       '''int''' i = binSearch(s.elements, elem)
-      '''if''' s.elements[i] == elem                           <font color=green>// Сравниваем найденное значение с искомым...</font color=green>
+      '''return''' s.elements[i] == elem                         <font color=green>// Сравниваем найденное значение с искомым...</font color=green>
 </code>
 Время выполнения {{---}} <tex>O(\log n)</tex>.

@@ Строка 14: / Строка 14: @@
 == Наивная реализация на массиве ==
-Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью отсортированного массива <tex>elements[0..n-1]</tex>.
+Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
 Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.

@@ Строка 88: / Строка 88: @@
   '''T''' predecessor(Set<T> s, T elem):
       '''int''' i = binSearch(s.elements, elem)
-      '''if''' s.elements[i] == elem '''and''' i != 0           <font color=green>// Элемент, предшествующий первому, не существует.</font color=green>
+      '''if''' s.elements[i] == elem '''and''' i > 0           <font color=green>// Элемент, предшествующий первому, не существует.</font color=green>
           '''return''' s.elements[i - 1]
       '''else'''
@@ Строка 100: / Строка 100: @@
 <code>
   '''T''' successor(Set<T> s, T elem):
-      '''if''' s.elements[0] <= elem '''&&''' s.elements[s.n] > elem         <font color=green>// Если элемент ''elem'' существует и не равен максимальному,</font color=green>
+      '''int''' i = binSearch(s.elements, elem)
-         '''int''' i = binSearch(s.elements, elem)                    <font color=green>// то ищем индекс элемента ''elem''</font color=green>
+     '''if''' s.elements[i] == elem '''and''' i < s.n - 1           <font color=green>// Элемент, следующий за последним, не существует.</font color=green>
-          '''return''' s.elements[i + 1]                               <font color=green>// и выводим следующий за ним элемент.</font color=green>
+          '''return''' s.elements[i + 1]
-      '''else'''                                                       <font color=green>// В противном случае</font color=green>
+      '''else'''
-          '''return''' ''null''                                            <font color=green>// возвращаем ''null''.</font color=green>
+          '''return''' ''null''
 </code>
 Время выполнения {{---}} <tex>O(\log n)</tex>.