Нужно ли умножать сложности?

Question

[zlodiak]

Скажите пожалуйста, я правильно понимаю, что для того чтобы определить сложность следующего алгоритма нужно, O(n) * O(n) = O(n^2)

#!/usr/bin/env python3

def reverse_letter(string):
    return ''.join([l for l in reversed(string) if l.isalpha()])

Я это делаю потому что reverse в худшем случае переберёт все элементы и for тоже переберёт все элементы. Таким образом итоговая сложность будет квадратичная

Answer 1

[Roman K]

Нет. Вот если бы у тебя было два вложенных цикла по string, то да. А тут сложность "складывается", потому что сначала O(n) — реверс, потом O(n) — создание цикла, потом O(n) — join. Но т.к. константы в сложности никому не нужны — это только O(n)

Но ты, конечно, не поверишь, поэтому вот тебе доказательство. Время линейно растёт вместе с N

Answer 2

[Павло Пономаренко]

Если я правильно понимаю, то reversed будет только один раз. Псевдокодом можно записать это так:

newStr = reversed(string);
for sym in newStr; // ..

То есть тут дважды используется линейный проход, а не линейный внутри линейного, а значит умножать не нужно - сложность линейная.