Этот алгоритм был написан для задачи подъема по лестнице LeetCode и работал при 20 мс. Я полагаю, что временная сложность составляет O (n), потому что эта ссылка https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7 говорит, что O (n) - это когда время работы линейно увеличивается по мере того, как размер входных данных увеличивается, что я и считаю здесь происходит
Мне было интересно, может ли кто-нибудь объяснить мне сложность времени здесь и почему это так. Любая дополнительная информация о том, как я мог бы получить ее за линейное время, если бы меня там уже не было, тоже поможет.
Вот мой код:
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0: return 1
else:
temp = []
for i in range(0, n + 1):
temp.append(i)
if temp[i] == 0:
temp[i] = 1
elif temp[i] > 1:
temp[i] = temp[i-1] + temp[i-2]
return temp[-1]