Простой запрос о временной сложности для Python "в" - PullRequest
Новая
       10

Простой запрос о временной сложности для Python "в"

0 голосов
/ 03 мая 2018

У меня есть функция strip_punctuation (text), которая принимает строку текста и удаляет все знаки пунктуации в ней, используя список знаков препинания. Я не уверен насчет сложности времени, будь то O (N) * N или O (N ^ 2). Я думаю, что это работает, где это O (N) для длины текста N, а затем O (N) для длины пунктуации. Может кто-то уточнить временную сложность этого кода? 

def strip_punctuation(text):
    punctuations = '''!()-[]{};:'"\,<>./?@#$%^&*_~'''
    stripped = ""
    for i in text:
        if i not in punctuations:
            stripped = stripped + i

    return stripped

1 Ответ

0 голосов
/ 03 мая 2018

Если N равно len(text), то это O (N): 

for i in text

Если M равен len(punctuations), то этот код O (M ^ 2): 

if i not in punctuations:
    stripped = stripped + i

Это потому, что все stripped (которое имеет длину> = M) должно быть скопировано M раз (stripped + i делает копию stripped).

Итак, если бы и text, и punctuations были входными данными, сложность была бы O (N) * O (M ^ 2), но в этом случае M является константой, поэтому сложность O (N) .

Обратите внимание, что если бы punctuations было очень очень большим, функция была бы очень-очень медленной, но ее сложность все равно была бы просто O (N), что означает, что это только в N раз медленнее, когда входной сигнал в N раз больше .

...