Если у вас фиксированный размер списка, этот код будет O (1)

Question

Скажем, например, что вы просматриваете буквы в списке, но вы должны проверить пунктуацию.Будет ли следующий код по-прежнему O (n), где n является максимальным количеством символов в строке?Я думаю, что это потому, что список пунктуации имеет фиксированный размер, так что если оператор все равно будет O (1) правильно?

punctuation = [',', '.', '?', '!', ':', ';', '"', ' ', '\t', '\n']   
for letters in line:
        if letters not in punctuation:
            word += letters

Answer 1

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

Если вы хотитеоптимизировать там, вы можете хранить знаки препинания в set, где in работает в постоянном времени:

punctuation = {',', '.', '?', '!', ':', ';', '"', ' ', '\t', '\n'} 
for letter in line:
    if letter not in punctuation:
        word += letter