Проверьте логи c, чтобы найти сложность времени и пространства для данного алгоритма.

Question

Мне нужно подтвердить правильность моего подхода к определению сложности времени и пространства для приведенного ниже алгоритма:

У меня есть входной список, и мы можем взять в качестве примера следующее: [1 100,1, 1,1,100,1,1,100,1], и давайте назовем данный список как стоимость. Я изменяю данный список согласно моему алгоритму ниже

Мой алгоритм:

1. L oop по списку (начиная с позиции 2) до конца списка ввода.
2. Мы выполняем следующую операцию: стоимость [i] = стоимость [i] + min (стоимость [i-1], стоимость [i-2])
3. В конечном итоге мы проверяем последние 2 элемента и взять минимальное значение из последних двух элементов = min = min (последний элемент, второй последний элемент).

Мой подход к вычислению сложности времени: 1. Для шага 1 = O ( n) 2. Для шага 2 = O (1) + O (n) (чтобы вычислить минимум среди двух элементов) 3. Для шага 3 = O (1)

Следовательно, сложность по времени = O (n ) + O (1) + O (n) + O (1) = O (n). Сложность пространства = O (n) [Простое предположение, что для хранения списка потребуется пространство]. Может кто-нибудь, пожалуйста, дайте мне знать, если мой подход для расчета сложностей действителен?

С уважением, Анубхав

Answer 1

Это довольно простой динамический алгоритм программирования c.

Ваши окончательные ответы верны, если вы используете список. Тем не менее, вы можете фактически увеличить сложность пространства до O(1), используя тот факт, что ваше динамическое программирование c является «без памяти» в том смысле, что нам нужны только два предыдущих значения для вычисления следующего значения. Таким образом, вместо сохранения всего списка, вы можете просто сохранить два «предыдущих» значения. Эта идея аналогична идее вычисления чисел Фибоначчи в O(1) пространстве и O(n) времени .