Главная /
Алгоритмы: построение и анализ /
Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть m и n размеры долей. Чему равно время работы алгоритма?
Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть m
и n
размеры долей. Чему равно время работы алгоритма?
вопрос
Правильный ответ:
min( O(n2*m), O(n*m2))
O(n2*m2)
max( O(n2*m), O(n*m2))
O(n*m)
Сложность вопроса
40
Сложность курса: Алгоритмы: построение и анализ
90
Оценить вопрос
Комментарии:
Аноним
Зачёт сдал. Иду кутить отмечать сессию интуит
17 май 2019
Аноним
Я сотрудник деканата! Срочно уничтожьте сайт и ответы по интуит. Не ломайте образование
11 сен 2017
Аноним
Если бы не опубликованные решения - я бы не осилил c этими тестами intuit.
20 сен 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \begin{pmatrix} 3 & 0 & 3 & 5 & 4\\ 3 & 1 & 2 & 2 & 3\\ \end{pmatrix} как будут выглядеть эти строки к концу второго шага?
- # Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
- # Какие утверждения верны?
- # Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...
- # В каком порядке идут вершины в "boundary-path"?