algorithm - 矩阵链乘法的蛮力方法的时间复杂度和空间复杂度是多少？

Question

我知道使用动态编程的时间复杂度和空间复杂度matrix chain multiplication是 O(n^3) 和 O(n^2)。

但我想知道这个问题的蛮力方法的时间和空间复杂度，可以用下面的代码来实现。

def MatrixChainOrder(p, i, j):
 
    if i == j:
        return 0
 
    _min = sys.maxsize
 
    for k in range(i, j):
 
        count = (MatrixChainOrder(p, i, k)
                 + MatrixChainOrder(p, k + 1, j)
                 + p[i-1] * p[k] * p[j])
 
        if count < _min:
            _min = count
 
    # Return minimum count
    return _min

#arr = [1, 2, 3, 4, 3]
#n = len(arr)
# p is array name
# i=1
#j= n-1

请详细说明...

标签： algorithmtime-complexitydynamic-programmingmatrix-multiplicationspace-complexity

Answer 1

堆栈深度是线性的，因此空间使用也是线性的。

至于时间，我们得到一个复发

T(1) = 1
T(n) = sum_{k=1}^{n-1} (T(k) + T(n-k)) = 2 sum_{k=1}^{n-1} T(k).

我们可以验证解决方案是

T(1) = 1
T(n) = 2 (3^(n-1))

所以运行时间是 Θ(3 ⁿ )。