временная сложность этого подхода

Итак, я читаю два файла и сохраняю каждую строку в двух разных списках соответственно. Теперь я должен проверить, присутствует ли строка в первом списке во втором списке.временная сложность этого подхода

При нормальной сравнении это потребуется O (N^2)

Но с использованием структуры данных графа на основе, как -

File1_visited [строка] = True

File2_visited [строка] = TRUE.

Я могу проверить, являются ли оба значения истинными, тогда строка присутствует в обоих файлах. Это делает его O (n).

Есть ли какой-либо другой подход, я могу уменьшить временную сложность и правильно ли я понял?

Пример сценария -

File1-

Текст1 Текст2 Text3 Text4

Файл2 -

Text5 Text7 Текст1 Текст2

Сравнение этих двух файлов.

источник

2016-07-22 Ryo

Что-то важное в ваших аналитических промахах: «Какова временная сложность построения и доступа к структуре графа?» Простым, довольно эффективным способом было бы загрузить оба файла в хэш-наборы, а затем проверить пересечение. Это очень похоже на ваш подход, но он использует стандартные структуры, которые очень эффективны для создания и доступа. Насколько велики ваши файлы? – jpmc26

Предполагая, что максимально 1000 строк. Также мое понимание правильное в отношении двух подходов. Я думал о хеш-наборе, но не тот же, что и второй подход, так как, возможно, вам придется проходить через каждый файл один раз – Ryo

Если ваш набор данных составляет всего 1000 строк, почему вы заботитесь о O (n)? Big O Notation для действительно, действительно больших наборов чисел/вычислений. https://en.wikipedia.org/wiki/Big_O_notation –

Да, вы прошли от O(n^2) до O(n). Возможно, вы захотите также изучить сложность пространства, вам нужно будет хранить график для одного из них, а для другого - меньше места. HashMap выглядит идеально для этой ситуации, если вам не нужна память или какой-либо другой массив, если его проще реализовать.

источник

2016-07-22 18:41:59 MathBunny

Ну, технически «O (n + m)», и это предполагает «HashMap», но OP сказал * «с использованием структуры данных на основе графа» *, что означает «TreeMap», и это будет «O ((n + m) ⋅log (n)) ', предполагая, что первый файл (' n') загружается в карту, а второй файл ('m') используется только для проверки карты, а не для создания второй карты, например OP фактически сказал. – Andreas

временная сложность этого подхода

ответ

Смежные вопросы