Сложность, как времени, так и пространства

Question

Я новичок в форуме, поэтому я надеюсь, что я делаю это правильно.

Я борюсь с выяснением сложности BigO. В частности, сложность времени. Я сейчас работаю над рекурсивной программой, которая вызывает себя дважды каждый рекурсор. Пример:

вычислить (I, J)

пограничные проверки

x = (вычислить (i-1, j) + вычислить (i, j-1)) /2;

возврат х;

Я думаю это O(2^n) время, потому что каждый вызов производит еще два. Это правильно? Это то же самое для сложности?

Answer 1

Я предлагаю вам использовать массив int или var-args, например, compute(int... val) для отправки 4 аргумента 2 для первой операции, последней 2 для второй операции, выполняемой вами внутри этого метода.

Возврат сложения двух операций из этого метода.

так что вы получите время O(n).

Answer 2

Время O(2^(m+n))и пространство O(1),

Для сложности времени:

• O(m,1) = O(m-1, 1) + O(1,1) = O(m-2,1) + 2O(1,1) = ... = O(m)
• O(m,2) = O(m,1) + O(m-1,2) = O(m) + O(m-1, 1) + O(m-2,2) = ... = O(m) + O(m-1) + ... + O(1) + O(1,2) = O(m^2)
• O(m,3) = O(m,2) + O(m-1,3) = O(m^2) + O(m-1, 2) + O(m-2,3) = ... = O(m^2) + - O((m-1)^2) + ... + O(1^2) + O(1,3) = O(2^m)
• O(m,4) = O(m,3) + O(m-1,4) = O(2^m) + O(m-1, 3) + O(m-3,4) = ... = O(2^m) + O(2^(m-1)) + ... + O(2^1) + O(1,4) = O(2^(m+1))
• O(m,5) = O(m,4) + O(m-1,5) = O(2^(m+1)) + O(m-1, 4) + O(m-3,5) = ... = O(2^(m+1)) + O(2^(m)) + ... + O(2^3) + O(1,5) = O(2^(m+2))
• ...
• O(m,n) = O(2^(m+n))

Для космической сложности:

он не использует бывшее пространство. это O(1)

PS

оптимизировать

def compute(i,j):
    result = [[0 for x in range(i)] for y in range(j)]
    for x in rangex(i):
        for y in xrange(j):
            if x == 0 or y == 0:
                result[x][y] = value(x,y); // compute(i,j) and (i,j) is edge
            else:
                result[x][y] = (result[x][y-1] + result[x-1][y]) / 2
    return result[i-1][j-1]

Это O(m*n) время и O(m*n) пространство.