Как уменьшить временную и пространственную сложность функции foo (n)? - PullRequest
0 голосов
/ 21 февраля 2020

Сложность по времени для функции 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 )

1 Ответ

3 голосов
/ 21 февраля 2020

Вы можете улучшить bar следующим образом:

def bar(n):
    return n * (n + 1) / 2

Это должно сократить foo до O (n).

Вы даже можете определить foo как:

def foo(n):
    return n * (n + 1) / 4 + n * (2 * n + 1) * (n + 1) / 12

Чтобы иметь функцию в O (1):)

...