Теоретическая оценка вычислительной сложности алгоритма в среднем, лучшем и худшем случаях, оцените асимптотическую сложность

Рейтинг: -1Ответов: 1Опубликовано: 19.05.2023

подскажите, пожалуйста, как оценить сложность этого алгоритма. Алгоритм заменяет нули на предыдущее не нулевое значение.

a = [3,1,4,0,0,0,0,0,5,0,4,0]
b = []
for i in a:
    b.append(i if i else b[-1])
print (b)

Я только третий день начала изучать питон, не очень понимаю.

python алгоритм сложность
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Ваш вопрос к пайтону особо отношения не имеет. Это относится к теме о сложности алгоритмов. В данном случае у вас сложность О(n) - линейная сложность. Естественно, как определять сложность алгоритмов в рамках одного ответа, объяснить невозможно. Поэтому рекомендую почитать литературу или погуглить тему "Оценка сложности алгоритмов".