Python: сложность функций с нарезкой кортежей и строк - PullRequest
Новая
       37

Python: сложность функций с нарезкой кортежей и строк

0 голосов
/ 29 марта 2019

Я не уверен, как вывести временную и пространственную сложность для следующих двух функций.

В следующей функции schedule - это кортеж строк, а course - строка. Я думаю, что сложность времени здесь O (n ^ 2), так как это O (n) для каждой рекурсии, где schedule[0] разрезается и затем объединяется в кортеж длиной n строк. Всего существует n рекурсий - следовательно, O (n * n) = O (n ^ 2).

Для той части, где происходит нарезка, а затем конкатенация, это потому, что я технически добавляю каждый элемент кортежа строк (schedule[1:]) к этой одной строке (schedule[0]) и что есть общее из n элементов в этом кортеже?

Для сложности пространства я думаю, что это также O (n ^ 2), так как каждый раз, когда происходит разрезание и конкатенация, создается новый кортеж пространства n. Это происходит для n рекурсий и отныне O (n * n) = O (n ^ 2). 

def drop_class(schedule, course):
    if schedule==():
        return ()
    elif schedule[0] == course:
        return schedule[1:]
    else:
        return (schedule[0],) + drop_class(schedule[1:], course)

В следующей функции letter и word являются строками. Я думаю, что сложность времени и пространства здесь также равна O (n ^ 2) для обоих по тем же причинам в вышеупомянутом примере. 

def remove(letter, word):
    if word[0] == " ":
        return " "
    if word[0] == letter:
        return remove(letter, word[1:])
    else:
        return word[0] + remove(letter, word[1:])

Однако я все еще не уверен, правильно ли я подхожу к проблемам, и был бы признателен за некоторые рекомендации по этому поводу. Спасибо.

...