2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Задача на доказательство оценки сложности алгоритма.
Сообщение31.12.2022, 17:26 
А как тогда вообще ответить на вопрос:"возможно ли?" Получается не особо чёткими формулировками интуитивно можно "доказать"?

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

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

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

 
 
 
 Re: Задача на доказательство оценки сложности алгоритма.
Сообщение01.01.2023, 15:55 
Maxim19 в сообщении #1575750 писал(а):
Это я и показал в решении, тут вопрос в строгом доказательстве, что остальные нельзя за О(1) делать
Насчет строгого доказательства не знаю. Не приходилось такой схоластикой заниматься.
А практически, чтобы был $O(1)$ для минимума и максимума, нужна сортивка данных (просто отсортированный массив или дерево какое). Но тогда никак не сделать добавление/удаление за $O(1)$.
Просто добавление/удаление за $O(1)$ легко сделать. Например, если это single float в 32 бита, то просто битовый массив заводите на $2^{32}$ элемента ($2^{29}$ байт - 512Мб). В нём множество и хранится. Но тогда минимум/максимум за $O(1)$ не будет.

 
 
 
 Re: Задача на доказательство оценки сложности алгоритма.
Сообщение01.01.2023, 19:47 
Аватара пользователя
zykov в сообщении #1575888 писал(а):
Не приходилось такой схоластикой заниматься
Это не схоластика, это совершенно разумный вопрос: какое есть ограничение снизу на сложность задачи.
zykov в сообщении #1575888 писал(а):
Но тогда минимум/максимум за $O(1)$ не будет
Будет, конечно. Проходимся по всему массиву и ищем минимум.

 
 
 
 Re: Задача на доказательство оценки сложности алгоритма.
Сообщение01.01.2023, 20:18 
mihaild в сообщении #1575896 писал(а):
Проходимся по всему массиву и ищем минимум.
Это $O(n)$.

 
 
 
 Re: Задача на доказательство оценки сложности алгоритма.
Сообщение01.01.2023, 20:42 
Аватара пользователя
zykov в сообщении #1575899 писал(а):
Это $O(n)$.
Нет, это $O(1)$. Это $2^{32}$ операций на каждый запрос, независимо от числа запросов.
Ну т.е. это конечно еще и $O(n)$, но важно, что это $O(1)$.

 
 
 [ Сообщений: 23 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group