Попытка выяснить время выполнения моей функции

Question

У меня есть этот код на Python для поиска самой длинной подстроки. Я пытаюсь выяснить асимптотическое время его запуска, и я пришел к ответу, но я не уверен, что это правильно. Вот код:

def longest_substring(s, t): 
    best = ' ' 
    for s_start in range(0, len(s)): 
     for s_end in range(s_start, len(s)+1): 
      for t_start in range(0, len(t)): 
       for t_end in range(t_start, len(t)+1): 
        if s[s_start:s_end] == t[t_start:t_end]: 
         current = s[s_start:s_end] 
          if len(current) > len(best): 
           best = current 
    return best 

Очевидно, что эта функция имеет очень медленное время работы. Это было спроектировано именно так. Мой подход заключался в том, что, поскольку существует цикл for с еще тремя вложенными петлями, время выполнения - это что-то вроде O (n^4). Я не уверен, что это правильно из-за того, что не каждый цикл повторяется по размеру ввода. Кроме того, предполагается, что s = t = n (размер ввода). Есть идеи?

Answer 1

Если вы не уверены, что это O (n^5), попробуйте рассчитать, сколько циклов вы используете для строки s (т. Е. Внешние две петли). Когда s_start == 0, внутренний цикл работает n + 1 раз; когда s_start == 1, внутренний цикл работает n раз и так далее, до s_start = n - 1, для которого внутренний цикл работает дважды.

Сумма

(n + 1) + (n) + (n - 1) + ... + 2 

является арифметической серии, для которых формула

((n + 1) + 2) * n/2 

который является O (N^2).

Дополнительный n-фактор исходит от s[s_start:s_end] == t[t_start:t_end], который является O (n).