@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 тоже переберёт все элементы. Таким образом итоговая сложность будет квадратичная
  • Вопрос задан
  • 217 просмотров
Решения вопроса 1
@deliro
Нет. Вот если бы у тебя было два вложенных цикла по string, то да. А тут сложность "складывается", потому что сначала O(n) — реверс, потом O(n) — создание цикла, потом O(n) — join. Но т.к. константы в сложности никому не нужны — это только O(n)

Но ты, конечно, не поверишь, поэтому вот тебе доказательство. Время линейно растёт вместе с N
5c6f07ce35b63943246212.png
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Если я правильно понимаю, то reversed будет только один раз. Псевдокодом можно записать это так:

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


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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
29 мар. 2024, в 10:00
10000 руб./за проект
29 мар. 2024, в 09:59
750 руб./в час
29 мар. 2024, в 09:55
50000 руб./за проект