Временная сложность моего поиска оптимального решения максимальной суммы несмежных

avatar
jeffng50
8 апреля 2018 в 08:26
116
1
0

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

Фон:

Сказать, если список ввода [1,2,3,4,5]

Запоминание должно быть [1,2,4,6,9]

И моя максимальная сумма равна 9, верно?

Мое решение:

  1. Я нахожу первое вхождение максимальной суммы в памятке (поскольку мы можем не выбрать последний элемент) [это O(N)]

  2. Затем я нахожу предыдущий элемент, выбранный по этой формуле:

    max_sum -= a_list[index]

Как и в этом примере, 9 - 5 = 4, где 4 находится в индексе 2, мы можем сказать, что предыдущий выбранный элемент равен "3", который также находится в индексе 2 в списке ввода.

  1. Я нахожу первое вхождение 4, которое находится в индексе 2 (я нахожу первое вхождение из-за той же концепции на шаге 1, поскольку мы могли не выбрать этот элемент в некоторых случаях, когда есть несколько одинаковых сумм вместе) [Также O(N), но...]

Проблема:

Третий шаг моего решения выполняется в цикле while, скажем, несмежное ограничение равно 1, максимальная сумма, на которую мы должны вернуться, когда длина списка равна 5, составляет 3 раза, примерно N//2 раза.

Но 3-й шаг использует функцию индекса Python для поиска первого вхождения предыдущей_суммы [которое равно O(N)] memo.index(that_previous_sum)

Таким образом, общая временная сложность составляет около O(N//2 * N)

Что равно O(N^2) !!!

Правильно ли я понимаю временную сложность? Или я ошибаюсь? Есть ли более эффективный способ вернуться к списку запоминания?

П.С. Извините за форматирование, если я сделал это неправильно, спасибо!

Источник

Ответы (1)

avatar
jeffng50
8 апреля 2018 в 09:22
0

Решено:

  1. Я зациклился сзади, проверяя, тот же предмет впереди или нет
  2. Если это то же самое, значит это не первое появление. Если нет, то это первое вхождение.
  3. Тада! Нет индексной функции Python для поиска по первому индексу! Находим его сейчас сзади

Поэтому общая временная сложность составляет около O(N//2 * N)

Теперь O(N//2 + 1), что равно O(N).