#time-complexity
#временная сложность
Вопрос:
Задан список списков, т.е. [[1,2,3],[4,5,6],[7,8,9]]: Какова временная сложность использования вложенных циклов For, чтобы увидеть, используется ли каждая цифра из 1-9 один и только один раз? Кроме того, какова была бы временная сложность, если бы входные данные теперь представляли собой единый комбинированный список, т.Е. [1,2,3,4,5,6,7,8,9]?
Комментарии:
1. Как ваш вопрос связан с названием? Вы не упоминаете «1-проход» или «N» в вопросе. Поскольку вы определили проблему, вам даже не нужен цикл, но только
return trueпотому, что ввод является константой (или, другими словами, ввода нет).
Ответ №1:
Что действительно важно, так это размер входных данных, а не формат. Либо у вас есть список из 9 элементов, либо 9 списков с 1 элементом, у вас все равно есть 9 элементов, которые нужно проверить в худшем случае.
Ответ на вопрос, как указано, будет O(1) следующим: потому что у вас есть ввод постоянного размера.
Если вы имеете в виду что-то вроде заданных N элементов, какова временная сложность проверки наличия всех чисел от 1 до N, тогда потребуется линейное время, т. Е. O(N) .
Действительно, можно использовать хеш-таблицу (например, набор python) и проверить, есть ли элемент уже в наборе, если его не добавлять. Обратите внимание, что при использовании этой конкретной опции вы получите ожидаемый (но не гарантированный, из-за потенциальных коллизий) алгоритм линейной временной сложности.