Задача на доказательство оценки сложности алгоритма.

[Maxim19]

Всех с наступающим. Есть такая задача: придумайте структуру для хранения действительных чисел, которая могла бы выполнять запросы "добавить элемент", "удалить элемент", "удалить максимальный элемент" и "удалить минимальный элемент", причем последние два выполняла бы за O(1). Постарайтесь также минимизировать время выполнения первых двух запросов. Можно ли сделать так, чтобы и они тоже выполнялись за O(1)? Ну и ответ таков, что нужен массив упорядоченный и вставлять элементы по бинарной штуке и очевидно, что второе условие про О(1) не получится сделать из соображений мол, вот числа проверять надо, структуру поддерживать, а с удалением и добавлением за константу много не учтём. Но как это доказывается формально? Я вот думаю, как обосновать, Но вот например для целых неповторяющихся чисел в диапазоне можно их записать в ячейки под номером, равным себе же(вроде называется хеш-таблицами). Для такого мои рассуждения на счёт того, что за константное время нельзя учесть всё, просто не работает. Помогите, если закончите старый год помощью, то в новом году помогать уже вам будут.

-- 30.12.2022, 05:02 --

Если что, то весь ответ от меня, так что возможно, что на счёт структуры нужной я ошибся.

[mihaild]

В такой постановке я могу реализовать все операции за $O(1)$ времени и памяти:

Используется синтаксис Python

class StructuraDannih:
  def add(self, x):
    pass
  def remove(self, x):
    pass
  def remove_max(self):
    pass
  def remove_min(self):
    pass
 

И пусть только попробует кто-то сказать, что она не выполняет запросы как надо.

[svv]

(Оффтоп)

Maxim19 в сообщении #1575614 писал(а):

Помогите, если закончите старый год помощью, то в новом году помогать уже вам будут.

А если весь год помогал, а в конце не смог, тогда как? Я, например, сейчас приболел.

[Maxim19]

Ну тогда помогать будут, но не так, как если накануне. Желаю поправиться к праздникам.

-- 31.12.2022, 00:25 --

mihaild в сообщении #1575638 писал(а):

В такой постановке я могу реализовать все операции за $O(1)$ времени и памяти:

Используется синтаксис Python

class StructuraDannih:
  def add(self, x):
    pass
  def remove(self, x):
    pass
  def remove_max(self):
    pass
  def remove_min(self):
    pass
 

И пусть только попробует кто-то сказать, что она не выполняет запросы как надо.

Простите, я плох в языках. На сколько я понял это шуточная штука? Типо в одну строку вызов функции. Но всё же кто может показать строгую формулировку?

[Geen]

Maxim19 в сообщении #1575614 писал(а):

нужен массив

А удаление первого элемента из массива - это константа?

[mihaild]

Maxim19 в сообщении #1575699 писал(а):

На сколько я понял это шуточная штука?

Это полушуточное указание на то, что в требованиях не указано, что структура должна хоть какие-то данные сообщать.
Поэтому она может просто ничего не делать и никаких элементов не хранить - проверить это всё равно нельзя.
Нужны какие-то операции, которые будут читать множество, например не только удалять максимум и минимум, но и получать их значения.

[Maxim19]

Тут же про то, чтобы после какой либо из этих операций можно было за такое же О() время такие же операции сделать. Это уже подразумевает информацию о всех элементах и правильность того, что мы действительно выводим максимальный элемент(к примеру). Или вы про другое?

-- 31.12.2022, 03:00 --

Geen
Как я понял, в таких задачах любая операция типа присвоения, удаления или же арифметическая операция считается за элементарную. Правда много нюансов по типу определения НОКа двух чисел. Если в задаче суть не в самом алгоритме НОКа, а например в сортировке какой нибудь по свойству НОКа, то можно и определение НОКа считать за элементарный "щелчок" в программе. Этим мне и не нравятся задачи на алгоритмы.

[mihaild]

В условиях же ничего не сказано про "вывод". Если просто добавить "вывод" (без требований), то подойдет такая реализация: просто сохраняем все запрошенные операции, а в момент, когда спросили - выполняем.
Правильная формулировка была бы, например, такой: добавить к операциям "получить значение максимального элемента" и "получить значение минимального элемента", и потребовать, чтобы они тоже выполнялись за $O(1)$.
Если это сделать, то уже можно будет доказать, что еще и вставку сделать за $O(1)$ не получится.

[Maxim19]

Я думаю, что именно это и подразумевали, иначе задачи тогда особо и нет. Если в вашей формулировке, как такие штуки доказывать? Просто охватить надо очень многое.

[mihaild]

Вы знаете, что сортировка, использующая только сравнения, не может работать быстрее чем за $O(N\log N)$? Предположите, что нужную нам тут структуру можно реализовать со всеми операциями за $O(1)$, и покажите, как, используя её, отсортировать массив быстрее.

[zykov]

Maxim19 в сообщении #1575614 писал(а):

"удалить максимальный элемент" и "удалить минимальный элемент", причем последние два выполняла бы за O(1).

За $O(1)$ нужно только эти два последних, что делается элементарно. Просто храните начало и конец отсортированного массива, они и содержат минимум и максимум.
Другие операции будут дольше, чем $O(1)$.

[Maxim19]

mihaild
Это я знаю, но кто сказал, что нельзя например использовать сортировку без сравнения?

-- 31.12.2022, 16:44 --

zykov
Это я и показал в решении, тут вопрос в строгом доказательстве, что остальные нельзя за О(1) делать

[mihaild]

Maxim19 в сообщении #1575750 писал(а):

Это я знаю, но кто сказал, что нельзя например использовать сортировку без сравнения?

Тут в другую сторону - с помощью этой структуры можно было бы реализовать сортировку сравнениями.
А т.к. этого сделать нельзя, то и структуру реализовать нельзя.
Это в предположении что действительные числа это просто что-то, что можно хранить и сравнивать. Если это конкретно например float32, то естественно можно за $2^{32} = O(1)$ операций сделать что угодно.

[Maxim19]

А как доказать, что более нет структур без сравнений, которые способы первые две реализовать за О(1)?

[mihaild]

Maxim19 в сообщении #1575754 писал(а):

А как доказать, что более нет структур без сравнений, которые способы первые две реализовать за О(1)?

Чтобы это доказать, надо это сначала сформулировать, что вряд ли получится (что значит, что структуры одинаковые?). И как "без сравнений" можно говорить о максимуме/минимуме?