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

Инструменты, алгоритмы и структуры данных

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

Какие утверждения справедливы о сложности решения задачи о топологической сортировке?

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа
практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n) независимо от m, где n - это число сортируемых элементов, m - число ограничений.
практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений(Верный ответ)
теоретически невозможно построить алгоритм временная и емкостная сложность которого была бы ниже чем O(n + m), где n - это число сортируемых элементов, m - число ограничений(Верный ответ)
практически невозможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений
Похожие вопросы
Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?
Какие утверждения справедливы о числе решений в задаче о топологической сортировке?
Укажите, какие утверждения справедливы для топологической сортировки:
"Инженерное" решение задачи о топологической сортировке, применимое в различных проблемных областях, предполагает, что на входе множество ограничений задает:
Какие утверждения справедливы о сложности операции вставки элемента в дерево поиска с n элементами?
Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?
Какие утверждения справедливы для задачи "Ханойская башня"?
Какие утверждения справедливы относительно представления исходных данных задачи?
Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера? Полагая, что проигрыш рассматривается как предшествование, укажите, какие последовательности соответствуют топологической сортировке игроков по результатам этих встреч?
Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?