База ответов ИНТУИТ

Алгоритмы: построение и анализ

<<- Назад к вопросам

Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть m и n размеры долей. Чему равно время работы алгоритма?

(Отметьте один правильный вариант ответа.)

Варианты ответа
min( O(n2*m), O(n*m2))(Верный ответ)
max( O(n2*m), O(n*m2))
O(n*m)
O(n2*m2)
Похожие вопросы
Чему равно время работы врямя работы алгоритма дискретного преобразования Фурье для многочлена степени n?
Чему равно время работы алгоритма обратного дискретного преобразования Фурье для многочлена степени n?
Время работы алгоритма Укконена для входного слова длины n равно
Пусть величину d протолкнули на шаге PUSH по ребру (u,v). Какой код тогда отвечает за изменение потоков и излишков?
Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...
Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?
Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это
Какое утверждение верно, если на шаге LIFT подымается вершина v?
Чему равна величина проталкиваемого потока на шаге PUSH?
Пусть в графе G пять разных минимальных покрывающих деревьев. Вова загодал K - одно из них. Пятя знает граф G но не знает какое минимальное покрывающее дерево, которое загадал Петя. Какие утверждения верны?