Пространственно-временная сложность рекурсивной реализации функции суммирования - PullRequest
Новая
       60

Пространственно-временная сложность рекурсивной реализации функции суммирования

0 голосов
/ 09 апреля 2020

Кто-нибудь может посоветовать пространственно-временную сложность приведенного ниже кода? Я знаю, что временная сложность должна быть O (n), потому что функция вызывается n раз, а пространственная сложность по крайней мере O (n) (из-за места в стеке), но передача функции [1:] в функцию приводит к увеличение сложности пространства? Я думаю, что [1:] создаст новую копию a , опуская первый элемент, верно? 

def sum(a):
    if len(a) == 1:
        return a[0]
    return a[0] + sum(a[1:])

Ответы [ 2 ]

1 голос
/ 09 апреля 2020

Сложность по времени похожа на тета (n ^ 2), потому что каждый раз, когда вы делаете [i:], вы в основном копируете список из i в конец, поэтому вам приходится повторять его. Что касается сложности пространства, в стеке приложений будут все ваши списки, которые вы будете вызывать, сначала список с n элементами, затем n-1 и т. Д. До 1, где вы начнете очищать стек. Таким образом, вы получите сложность тэта (n ^ 2) для этого тоже.

0 голосов
/ 09 апреля 2020

В качестве рекурсивной функции, если не применяется оптимизация tail-call , она, безусловно, будет иметь пространственную сложность не менее O(n) в этом случае, учитывая ее выполнение в стеке памяти. Но давайте проанализируем это далее:

Сложность времени

Мы знаем, что сумма является рекурсивной, и ее критерий остановки - это когда входной массив имеет одну длину. Итак, мы знаем, что Sum будет вызываться по крайней мере O(n) раз в худшем случае, учитывая входной массив размером n. Рассмотрим рекурсию того, чем она является, то есть a l oop.

Внутри функции, однако, у нас есть операция среза. Операция среза l[a:b] равна O(b-a), поэтому эта операция будет иметь сложность O(n-1) при первом запуске, O(n-2) при втором запуске и т. Д. Мы считаем, что примитивно, он будет выполнять копию всего массива. Общая временная сложность для этой функции должна составлять O(n^2), поскольку она создает срез для каждого элемента в массиве размером n.

Пространственная сложность

Теперь говорим о месте в памяти. 

len(a) == 1

Здесь у нас есть одна копия из возвращаемого значения len (a). 

return a[0]

& 

    return a[0] + sum(a[1:])

В в обеих строках выше у нас будет еще одна копия значения, которая будет сохранена в адресе возврата функции. Срез также имеет пространственную сложность O(n).

Видя это, и учитывая, что компилятором не применяются существенные оптимизации, такие как сокращение , мы говорим, что пространство сложность этой функции составляет O(n), потому что она создаст константу количество копий для каждого ввода И выполнит операцию среза в массиве размером n.

Поскольку мы уже говорили вначале эта рекурсия похожа на al oop, не учитывая оптимизацию хвостового вызова, вся эта функция будет выполняться n раз в худшем случае. Программа будет увеличивать стек памяти функции до тех пор, пока не достигнет критерия остановки, пока, наконец, не сможет «вытолкнуть» возвращаемые значения из стека вызовов. Таким образом, общая сложность пространства также составляет O(n*log n) (поскольку при каждом выполнении входной массив уменьшается).

Ps:

Я также считал, что len(a) O(1) сложность времени, в соответствии с это .

...