Какова жесткая граница для времени выполнения этого кода в худшем случае? - PullRequest
Новая
       6

Какова жесткая граница для времени выполнения этого кода в худшем случае?

0 голосов
/ 19 сентября 2018

Итак, у меня есть код ниже, который проверяет, есть ли шаблон в P, который находится внутри S. Мне нужно найти точную границу для времени выполнения наихудшего случая, но я не уверен, как это сделать.Вся концепция наилучшего и наихудшего сценариев времени выполнения сбивает меня с толку.Если бы вы могли объяснить, как найти их для псевдокода ниже, это было бы огромной помощью!

Требуется: P[0, ... , m − 1], S[1, ... , n], f or 1 ≤ m ≤ n.

f = false
i = 0
while (i ≤ n − m) AND ¬f do
    i = i + 1
    f =true
    for j = 0;(j < m) AND f; j = j + 1 do
        f = f AND (P[j] == S[i + j])
    end for
end while
return i
...