Сложность по времени для функции foo равна O (n ^ 2), но мне нужно уменьшить ее и, похоже, не могу понять.
def bar ( n ): if n == 0 : return 0 else : return n + bar ( n - 1 ) def foo ( n ): if n == 0 : return 0 else : return bar ( n ) + foo ( n - 1 )
Вы можете улучшить bar следующим образом:
bar
def bar(n): return n * (n + 1) / 2
Это должно сократить foo до O (n).
foo
Вы даже можете определить foo как:
def foo(n): return n * (n + 1) / 4 + n * (2 * n + 1) * (n + 1) / 12
Чтобы иметь функцию в O (1):)