О (n + m) и O (n) обозначения эквивалентны, если m

Question

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

Answer 1

По сути, Робин-Карп выражает свою асимптотическую запись как O(m+n) как средство для выражения того факта, что требуется линейное время относительно m+n, а не просто n. По сути, переменные m и n должны что-то значить, когда вы используете асимптотическую запись. В случае алгоритма Робина-Карпа n представляет длину текста, а m представляет суммарную длину как текста, так и шаблона. Обратите внимание, что O(2n) означает то же самое, что и O(n), потому что O(2n) все еще является линейной функцией от просто n. Однако в случае с Робин-Карпом m+n на самом деле не является функцией , а просто n. Скорее, это функция как m, так и n, которые являются двумя независимыми переменными. Таким образом, O(m+n) не означает то же самое, что и O(n) так же, как O(2n) равняется O(n).

Надеюсь, это имеет смысл. : -Р

Answer 2

Есть несколько сценариев, в которых высказывание сложности в форме O(n+m) подходит, чем просто высказывание O(max(m,n)).

Сценарий :

Рассмотрим BFS (Поиск в ширину) или DFS (Поиск в глубину) в качестве сценария.Это будет более интуитивно понятно и даст больше информации, чтобы сказать, что сложность O(E+V), чем max{E,V}.Первый синхронизирован с фактическим алгоритмическим описанием.

Answer 3

m и n измеряют различные размеры входных данных.Текст длины n и шаблоны длины m - это не то же самое, что текст длины 2n и шаблоны длины 0.

O(m+n) говорит о том, что сложность пропорциональна обоимдлина текста и длина узоров.