Какова сложность алгоритма и как она подсчитана?

#python #алгоритм #python_3x

Какова сложность алгоритма поиска подстроки в строке, и как она подсчитана? Прошу
объяснить. (алгоритм сыроват, но упрощён в качестве примера и для понимания)

text='bla-bla-this-bla'
subtext='this'
for i,element in enumerate(text):
    if element == subtext[0]:
        if subtext == text[i:i+len(subtext)]:
            print(i)

    

Ответы

Ответ 1

Пусть:

n = len(text)
m = len(subtext)


Очевидно что цикл for сделает в худшем случае n итераций, внутри каждой итерации
в худшем случае мы делаем слайс text[i:i+len(subtext)], который выполняется за O(m),
а затем сравнение за те же O(m), в итоге получаем O(nm).