Необходимо построить алгоритм, который находит минимальный элемент в куче с максимальным свойством и доказать, что он оптимальный (т.е. если построенный алгоритм работает за время O(f(n)), то любой алгоритм работает за Ω(f(n)). Считать, что алгоритм не знает элементы заранее, куча хранится в памяти как массив a и алгоритм может за один запрос i узнать элемент a[i]).

задан 6 Апр 2:08

изменен 7 Апр 19:52

@Наум Петров: что означает фраза "находит минимальный элемент в куче на максимум"? Она чисто грамматически непонятна.

(6 Апр 2:19) falcao

@falcao, есть алгоритм "сортировка кучей"... видимо здесь из этой оперы...

(6 Апр 2:49) all_exist

@all_exist: возможно, одно как-то связано с другим, но смысл фразы это не проясняет, не говоря о её грамматическом строении.

(6 Апр 3:03) falcao

@falcao @all_exist исправил, имелось в виду куча с максимальным свойством

(7 Апр 19:53) Buba

@Наум Петров: теперь дело за малым -- узнать определение "кучи с максимальным свойством" :)

(7 Апр 20:44) falcao

@falcao :) Это куча, значения потомков каждой вершины которой меньше значения самой вершины. И ещё у каждой вершины по два потомка.

(7 Апр 23:19) Buba

@Наум Петров, в бинарной максимальной куче минимальный элемент должен находиться среди листьев. Отсюда как вариант: найти минимум среди листьев (т.е. второй половины массива хранящей кучу). Сложность O(n)

(8 Апр 0:34) Квантиль

@Наум Петров: а это не то же самое, что корневое двоичное дерево, если говорить на математическом, а не на "прикладном" языке? И верно ли, что по два потомка есть у всех вершин кроме "нижних", которые называются листьями?

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

(8 Апр 0:47) falcao
(8 Апр 0:55) Квантиль

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

(8 Апр 2:18) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×239
×153
×72

задан
6 Апр 2:08

показан
146 раз

обновлен
8 Апр 2:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru