Задача
Спросил Grim,
Итак, по просьбе Fortunato выкладываю задачку.
Задача: Доказать, что массив N является перестановкой массива M. Выбрать наиболее быстрый алгоритм (большим плюсом будет ещё показать его эффективность).
Первый решивший — молодец и няша ^_^
Задача: Доказать, что массив N является перестановкой массива M. Выбрать наиболее быстрый алгоритм (большим плюсом будет ещё показать его эффективность).
Первый решивший — молодец и няша ^_^
9 ответов
На простом неотсортированном массиве M сложность поиска элемента O(M) а удаления O(1) + мы проходим по массиву N, тогда сложность алгоритма будет O(N*M).
Однако, при смене контейнера, к примеру, на хешированный словарь, можно сократить сложность поиска до O(logM), тогда и общая сложность алгоритма упадет.
Что скажете? Комментарии? Замечания? Предложения?
Если отсортировать оба массива, после чего просто сравнить их, можно получить O(nlogn) (n==m, иначе вообще проверять перестановки нет смысла), что является оптимальным.