def fastfib(n, fib_dict = {0: 1, 1: 1}): if n not in fib_dict: fib_dict[n] = fastfib(n-1, fib_dict) + fastfib(n-2, fib_dict) return fib_dict[n]
Я думаю, что сложность здесь n ^ 2, но я не уверен.
Поскольку вы заполняете словарь значениями n , нижняя граница равна O (n) .Однако, поскольку вы выполняете только операции с постоянным временем для каждой n , (операция поиска в словаре Pythons равна O (1) , хотя и амортизирована), этот алгоритм должен быть O (n) (амортизировано).Этот метод сохранения уже вычисленных значений в таблице называется памятка .