2014-01-22 5 views
8

Я прочитал эту статью Retiring a Great Interview Problem, автор придумал проблему 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. 

мемоизации алгоритм из Retiring a Great Interview Problem

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; 
} 
+0

Решение не является оптимальным, оно только обновляет memoized карту, когда результат ввода строки является нулевым, должен обновляться во всех случаях! –

+1

Это правильно. Обратите внимание, что 'segSuffix' называется только recusively, если' prefix' находится в слове в 'dict'. Если этот рекурсивный вызов возвращает non-'null', вызывающий абонент также сразу же возвращает его в стек. Другими словами, как только вызов 'segSuffix' возвращает значение, отличное от' null', алгоритм никогда не вызывает 'segSuffix' снова, поэтому значение non-' null' не нужно запоминать. – Alp

+0

@Alp Ницца, спасибо. В этом случае достаточно только массива логических значений, поскольку мы всегда можем ссылаться на суффикс как на его индекс во всей строке ввода. –

ответ

4

Интуиция

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

Поскольку рекурсивный вызов выполняется перед вводом значения в мемоизации -cache, последние (кратчайшие) суффиксы будут сначала кэшироваться.Это связано с тем, что функция сначала вызывается с длиной строки 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

Индукционный шаг

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

Шаг 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, что завершает доказательство.

+1

Большое спасибо за математическое доказательство! – mitchelllc

-1

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

принимают входной строки, ааааа

есть Н х 'а' строки

Н-1 'AA' строки

и так на

+0

спасибо за быстрый ответ! Не могли бы вы объяснить, почему максимальное количество словарных слов, которые оно может содержать, - N? – mitchelllc

+1

@mitchellc: Потому что каждое слово будет иметь хотя бы 1 букву. –

+0

может кто-нибудь сказать мне, почему downvote? – Pita

0

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

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

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

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

Примечание: только с предположением для стоимости какdict.contains(input) и memoized.containsKey(input) являются O (1) поэтому сложность O (N^2).

+0

Не могли бы вы объяснить, почему мы можем разбить его на 'N * (N-1)/2 сегмента'? Я думаю, что это должно быть '2^N', так как для каждой буквы во входной строке она может содержать или не содержать в сегменте. – mitchelllc

+0

@mitchelllc, чтобы сделать сегмент, нам нужен один старт и одна конечная точка, поэтому в индексе 'i' конечные точки сегмента, начиная с него, это' i + 1', 'i + 2', ... Итак, индекс 0 может иметь n сегментов, индекс 1 имеет n-1 сегментов ... И формула для суммы от n до 1 равна n * (n-1)/2 –

+0

ну, я все еще смущен. Как пояснил автор в статье, «который уменьшает анализ, чтобы определить количество возможных сегментирования. Я оставляю это как упражнение для читателя (с этим намеком), чтобы определить, что это число равно O (2^n) .' (см. «Общее решение» в http://thenoisychannel.com/2011/08/08/retiring -a-great-interview-problem /) – mitchelllc

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