Что такое время и пространственная сложность, чтобы найти максимальную сумму в треугольнике сверху вниз

Алгоритм следующий: какова наилучшая и наихудшая временная и пространственная сложность для нахождения максимальной суммы в треугольнике сверху вниз.

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

}

}

Любая помощь приветствуется. Заранее спасибо.


algorithm time-complexity dynamic-programming space-complexity
person dhamini poornachandra    schedule 14.01.2018    source источник
comment
Подсказка: наилучшая временная и пространственная сложность достигается путем нахождения ее снизу вверх :)   -  person גלעד ברקן    schedule 14.01.2018
comment
Непонятна ваша формулировка: как определяется сумма в треугольнике? Вы имеете в виду треугольную область ячеек в таблице?   -  person meowgoesthedog    schedule 14.01.2018
comment
@meowgoesthedog geeksforgeeks.org/maximum-path-sum-triangle ссылается на это ссылка для уточнения.   -  person dhamini poornachandra    schedule 14.01.2018
comment
Вы никогда не должны ссылаться на ссылку для описания проблемы, потому что это пустая трата времени для читателей. Вы должны включить минимальное достаточное описание - MVCE (минимальный проверяемый конкретный пример)   -  person meowgoesthedog    schedule 14.01.2018

Ответы (1)


arrow_upward
1
arrow_downward

Подсказка находится в первой строке кода:

For each ELEMENT in particular ROW and COLUMN

Вложенных циклов нет. Следовательно, временная сложность прямо пропорциональна общему количеству элементов, т. е. O(N^2), где N — количество строк.

person meowgoesthedog    schedule 14.01.2018