Граф имеет n вершин. Какое наибольшее количество сравнений длин ребер сделает алгоритм Прима в худшем случае?

задан 25 Дек '16 9:07

10|600 символов нужно символов осталось
1

Если действовать "бесхитростно", то надо рассмотреть полный граф с $%n$% вершинами. На первом шаге выбрали точку, она имеет $%n-1$% соединение. Для выявления ребра минимальной стоимости нужно $%n-2$% в худшем случае сравнения. Теперь проводим ребро, и сравниваем рёбра, которые соединяют одну из двух вершин поддерева с вершинами дополнения. Это $%2(n-2)$% рёбер; сравнений на единицу меньше, то есть $%2n-5$%. И так далее.

В итоге надо просуммировать величины $%k(n-k)-1$% по $%k$% от $%1$% до $%n-1$%. Должен получиться кубический многочлен. Суммирование даёт $%\frac{(n-2)(n-1)(n+3)}6$%.

Интересно, что можно слегка "схитрить" и подсчитать всё быстрее, зная, что при $%n=1$% и $%n=2$% формула должна давать 0, то есть многочлен делится на $%(n-1)(n-2)$%. Тогда частное подбирается по двум ненулевым значениям. При $%n=3$% нужно 2 сравнения, а при $%n=4$% их 7. Деление на $%(n-1)(n-2)$% даёт значения $%1$% и $%\frac76$%. Отсюда сразу понятно, что линейная функция имеет вид $%\frac{n+3}6$%.

ссылка

отвечен 25 Дек '16 14:06

Спасибо, доступно объяснили!)

(29 Дек '16 6:45) Sadykh
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×751
×195
×41

задан
25 Дек '16 9:07

показан
510 раз

обновлен
29 Дек '16 6:45

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

по почте:

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

по RSS:

Ответы

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

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