Как я могу вычислить временную сложность этого кода?

Question

def long_common_prefix(input_list):


    for i in range(1, len(input_list)):
        input_list[0] = get_prefix(input_list[0], input_list[i])

    return input_list[0]

def get_prefix(s1, s2):

    p1 = p2 = 0
    e1, e2 = len(s1), len(s2)
    currLongest = ''
    while p1 != e1 and p2 != e2:
        if s1[p1] == s2[p2]:
            currLongest += s1[p1]
            p1 += 1
            p2 += 1
        else:
            break

    return currLongest

Это код, который вычисляет самый длинный общий префикс строк в списке. Так, например, ['abcd','abc','ab'] даст мне 'ab'. Код работает хорошо, но я не знал, как определить временную и пространственную сложность кода.

В long_common_prefix есть только один цикл O(N), а внутри цикла он вызывает помощника get_prefix. Поскольку get_prefix будет O(N) и будет работать внутри одного цикла, будет ли O(N^2), где N - длина строки?

Спасибо.

Answer 1

Вы правы, за исключением того, что N - это длина списка ввода, но get_prefix работает со строками в линейном времени (и пространстве), а длина строк никоим образом не связана с длиной список ввода.

Сложность get_prefix равна O(M), где M - длина общего префикса.

Сложность времени: O(N*M)
Пространство сложность: O(M)