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

[Maxim19]

А как тогда вообще ответить на вопрос:"возможно ли?" Получается не особо чёткими формулировками интуитивно можно "доказать"?

[mihaild]

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

[Maxim19]

Ну и ну, какие сложные слова. Вроде что то понял: у нас есть множество, из за того, что это действительные числа, мы модем только сравнивать, а значит любые сортировки сравнением можем делать. Ну а построив дерево сравнений, найдём высоту и так докажем, что быстрее чем за $O(NlogN)$ быстрее нельзя. Всё верно понял?

[mihaild]

Нет. Тут важно, что такое "действительные числа" - какие операции нам с ними доступны.
Если нам доступно только сравнение, то мы сможем из нашей структуры сделать сортировку, основанную на сравнении (никаких деревьев тут строить не понадобится, передоказывать нижнюю оценку на сложность сортировки не нужно).
Если нам доступно что-то еще, то нужно уточнять, что, и, в зависимости от этого уточнения, может оказаться что нашу структур сделать и можно. Насколько я помню, даже вопрос о том, можно ли отсортировать целые числа за линейное время, если кроме сравнения нам доступны битовые операции - открыт.

[zykov]

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

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

Насчет строгого доказательства не знаю. Не приходилось такой схоластикой заниматься.
А практически, чтобы был $O(1)$ для минимума и максимума, нужна сортивка данных (просто отсортированный массив или дерево какое). Но тогда никак не сделать добавление/удаление за $O(1)$.
Просто добавление/удаление за $O(1)$ легко сделать. Например, если это single float в 32 бита, то просто битовый массив заводите на $2^{32}$ элемента ($2^{29}$ байт - 512Мб). В нём множество и хранится. Но тогда минимум/максимум за $O(1)$ не будет.

[mihaild]

zykov в сообщении #1575888 писал(а):

Не приходилось такой схоластикой заниматься

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

zykov в сообщении #1575888 писал(а):

Но тогда минимум/максимум за $O(1)$ не будет

Будет, конечно. Проходимся по всему массиву и ищем минимум.

[zykov]

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

Проходимся по всему массиву и ищем минимум.

Это $O(n)$.

[mihaild]

zykov в сообщении #1575899 писал(а):

Это $O(n)$.

Нет, это $O(1)$. Это $2^{32}$ операций на каждый запрос, независимо от числа запросов.
Ну т.е. это конечно еще и $O(n)$, но важно, что это $O(1)$.