251
правка
Изменения
→Асимптотика
* Если стадия <tex>k</tex> имеет тип (2) или (3), стоимость <tex>cost_k = suf_k + 1</tex>.
В случае стадии типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение той же стадии, являются
стоимостью последующих этапов. Общее количество сравнений выполняемых алгоритмом это сумма стоимостей. Мы хотим доказать, что <tex> \sum cost < 2 \sum shifts</tex>. Во второй <tex> \sum </tex> длину последнего сдвига заменим <tex>m</tex>. Даже с этим предположением, мы имеем<tex> \sum shifts < |t|</tex>, и если неравенство выполняется, тo <tex> \sum cost < 2|t|</tex>.
Для стадии типа (1), <tex>cost_k = 1</tex> очевидным образом меньше, чем <tex>2shift_k</tex>, так как <tex>shift_k > 0</tex>. Для стадии типа (2), <tex>cost_k = suf_k + 1 \leqslant 2 shift_k</tex>, по определению длинных сдвигов. Остается рассмотреть стадии типа (3). Так как в этой ситуации мы имеем <tex>shift_k < suf_k</tex>, единственный вариант, что обычный сдвиг применяется на стадии <tex>k</tex>. Тогда мы запоминаем этот момент. На следующей стадии, <tex>k + 1</tex>, мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на стадии <tex>k + 1</tex>, основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости стадии <tex>k</tex>), которые используем позже.
* Случай (а): <tex>suf_k + shift_k \leqslant |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_k - suf_{k+1} < shift_{k + 1}</tex>. Таким образом, <tex>cost_k = sufk + 1 \leqslant suf_{k+1} + shift_{k+1} + 1 \leqslant shift_k + shift_{k + 1}</tex>.
* Случай (б): <tex>suf_k + shift_k > |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_{k+1} + shift_k + shift_{k + 1} \geqslant m</tex>. Тогда <tex>cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 1}</tex>.Можно считать, что на стадии <tex>k + 1</tex> случай (б) имеет место, потому что это дает нам верхнюю границу <tex>cost_k</tex> (это верно, если <tex>shift_k \geqslant 2</tex>, случай <tex>shift_k = 1</tex> можно обрабатывать напрямую). Если стадия <tex>k + 1</tex> типа (1), то <tex>cost_{k + 1} = 1</tex>, а затем <tex>cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}</tex>, что даже лучше, чем ожидалось. Если на стадии <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} \leqslant shift_{k + 1}</tex>, то мы получим то, что ожидалось: <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1}</tex>.Последняя ситуация для рассмотрения, когда на стадии <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} > shift_{k + 1}</tex>. Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на стадии <tex>k + 1</tex>.Таким образом, приведенный выше анализ также применяется на стадии <tex>k + 1</tex>, и, так как только случай (а) может произойти тогда мы получаем <tex>cost_{k + 1} \leqslant shift_{k + 1} + shift_{k + 2}</tex>. Мы, наконец, получаем <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1} + shift_{k + 2}</tex>.Последний аргумент, доказывающий первый шаг индукции: если все стадии <tex>k</tex> до <tex>k + j</tex> таковы, что <tex>suf_k > shift_k,... , suf_{k + j} > shift_{k + j}</tex>, то <tex>cost_k + ... + cost_{k + j} \leqslant 2shift_k + ... + 2shift_{k + j} + shift_{k + j + 1}</tex>. Пусть <tex>k'</tex> первый этап после этапа <tex>k</tex> такой, что <tex>suf_{k'} \leqslant shift_{k'}</tex>. Целое число <tex>k'</tex> существует потому, что иначе получим бесконечную последовательность сдвигов с уменьшающейся длиной. После этого мы получим <tex>cost_k + ... + cost_{k'} \leqslant 2shift_k + ... + 2shift_{k'}</tex>.Это показывает нам, что <tex> \sum cost_k \leqslant 2 \sum shift_k</tex>, что и требовалось.}}
==См. также==
