Какие утверждения справедливы о сложности решения задачи о топологической сортировке?
(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n) независимо от m, где n - это число сортируемых элементов, m - число ограничений.
практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений(Верный ответ)
теоретически невозможно построить алгоритм временная и емкостная сложность которого была бы ниже чем O(n + m), где n - это число сортируемых элементов, m - число ограничений(Верный ответ)
практически невозможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений