Наивное доказательство сложности соответствия строк? - PullRequest
0 голосов
/ 21 февраля 2019

Я пытаюсь сделать доказательство того, как наивный String Matcher (http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/naiveStringMatch.htm) равен O ((n - m + 1) m) в худшем случае.
Но я не уверенкак начать.

Например, я не могу просто сказать, что «цикл for в строке 3 выполняется не более n - m +1 раз, а цикл while в строке 5 выполняется не более mраз "для формального доказательства? Я так не думаю, верно?
Спасибо

...