Вопрос: Временная сложность алгоритма замещения


Я прочитал эту статью Уход за большой проблемой интервью , автор придумал work break проблемы и дал три решения. Эффективный использует memoization алгоритм, и автор сказал, что его наихудшая временная сложность O(n^2) поскольку the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes,

Однако мне трудно понять, почему это O(n^2), Может кто-нибудь, пожалуйста, дайте мне подсказку или доказательство?

Work Break Problem: 
    Given an input string and a dictionary of words,
    segment the input string into a space-separated
    sequence of dictionary words if possible. For
    example, if the input string is "applepie" and
    dictionary contains a standard set of English words,
    then we would return the string "apple pie" as output.

Алгоритм memoization из Уход за большой проблемой интервью

Map<String, String> memoized;

String SegmentString(String input, Set<String> dict) {
      if (dict.contains(input)) 
          return input;
      if (memoized.containsKey(input) {
          return memoized.get(input);
      }
      int len = input.length();
      for (int i = 1; i < len; i++) {
          String prefix = input.substring(0, i);
          if (dict.contains(prefix)) {
              String suffix = input.substring(i, len);
              String segSuffix = SegmentString(suffix, dict);
              if (segSuffix != null) {
                  return prefix + " " + segSuffix;
              }
          }
      }
      memoized.put(input, null);
      return null;
}

9


источник


Ответы:


Интуиция

(ясно, что худший случай - тот, где нет решений, поэтому я сосредоточен на этом)

Поскольку рекурсивный вызов выполняется перед помещением значений в кеш memoization, последние (кратчайшие) суффиксы будут сначала кэшироваться. Это связано с тем, что функция сначала вызывается с длиной строки N, которая затем вызывает себя с длиной строки N-1, которая затем .... с строкой len 0, которая кэшируется и возвращается, тогда строка длиной 1 кэшируется и возвращает, ..., длина N кэшируется и возвращается.

Как подсказывает подсказка, только суффиксы получаются кэшированными, и их только N. Это означает, что к тому моменту, когда функция верхнего уровня получает результат первый  рекурсивный вызов (т. е. в суффиксе длины N-1), кэш уже заполнен суффиксами N-1.

Теперь, предположив, что последние суффиксы N-1 уже кэшированы, for-loop должен сделать N-1 рекурсивные вызовы, каждый из которых принимает O (1) (поскольку ответ уже кэширован), суммируя O (N). Однако (предварительное) построение кэша последнего N-1 принимает O (N ^ 2) (объясняется ниже), суммируя с O (N) + O (N ^ 2) = O (N ^ 2).


Доказательство математической индукцией

Это объяснение можно легко перевести на формальное доказательство с использованием индукции. Вот суть этого:

( f(N) число операций, необходимых для выполнения функции на входе длины N)

Гипотеза индукции  - существует постоянная c S.T. f(N) < c*N^2,

Основной корпус  тривиально - для строки длины 1 вы можете найти постоянную c такой, что f(1) < c*N^2 = c 

Шаг индукции

Повторение порядка вещей происходит:

Шаг 1: функция сначала вызывает себя в суффиксе длины N-1, создавая кэш, содержащий ответ для последних суффиксов N-1

Шаг 2: функция затем называет себя O (N) больше раз, каждый из которых принимает O (1) (благодаря этому тесту: if (memoized.containsKey(input)), и тот факт, что кеш уже заполнен Шаг 1 ).

Таким образом, мы получаем:

f(N+1) = f(N) + a*N <   (by the hypothesis)
       < c*N^2 + a*N <  (for c large enough)
       < c*N^2 + 2*c*N + c =
       = c*(N+1)^2

Таким образом, мы получили f(N+1) < c*(N+1)^2, что завершает доказательство.


5



Сначала для данной строки с длиной N мы можем разбить ее на N * (N-1) / 2 сегментов , и проверьте, содержится ли каждый сегмент в словаре. Эта стоимость равна O (N ^ 2)

Вернитесь к своему коду, начните с строки N, мы разделим ее на две меньшие строки, длину «А» , а также 'N - a' , И для каждой подстроки (или префикса) начинаются с 0 и заканчиваются на «А» , мы проверяем его только один раз!

Из каждого сегмента N - a он также проверяет каждый из своих префиксов один раз и храните его в запомненной таблице , таким образом, этот шаг позволит убедиться, что в следующий раз, когда мы совершим тот же самый шаг, разделим строку на этом ровном месте, нам нужно только вернуть результат без дальнейшей работы (с предположением, что карта будет извлекать и возвращать результат для конкретной строки в O (1)). Этот шаг сохранения и получения также гарантирует, что захват и разделение выполняются только один раз.

Итак, после первой и второй точки мы заключаем, что существует только N * (N - 1) / 2 сегмент, который будет рассмотрен на только один раз , что приводит к тому, что стоимость O (N ^ 2)

Заметка


0



Если вход имеет длину N, тогда максимальное количество словарных слов, которое это могло бы содержать, было бы N. Поэтому вам нужно проверить все различные комбинации длины 1..N. который представляет собой N (N-1) / 2

введите строку ввода, aaaaa

есть N x 'a' строки

Строки N-1 'aa'

и так далее


-1