algorithm - 从上到下求三角形最大和的时间和空间复杂度是多少

Question

算法如下:从上到下求三角形最大和的最佳和最差时间空间复杂度分别是多少

For each ELEMENT in particular ROW and COLUMN

{

If ( ELEMENT is FIRST ELEMENT  of ROW)

{

MAX_SUM[ROW][COLUMN] = ELEMENT + FIRST element of (ROW-1)

}

Else If (ELEMENT is LAST ELEMENT of ROW)

{

MAX_SUM[ROW][COLUMN] = ELEMENT + LAST element of (ROW-1)

}

Else

{

MAX_SUM[ROW][COLUMN] = ELEMENT + maximum( element at [ROW-1][COLUMN-1], element at [ROW-1][COLUMN])

//recursive formula calculating max_sum at each point from all possible paths till that point

}

}

感谢任何帮助。提前谢谢你。

Answer 1

线索在代码的第一行:

For each ELEMENT in particular ROW and COLUMN

没有嵌套循环。因此，时间复杂度与元素总数成正比，即O(N^2)，其中N 是行数。