Как изменится временная сложность от грубой силы до решения рекурсии?

Question

Это проблема, я работаю над

Я реализовал грубое силовое решение и разделяй и (рекурсивное) решение властвуй. Они оба работают с этим входом (от 1 до 4)

Для решения грубой силы я сделал все подмножества {1,2,3,4}, перебирал все подмножества и проверял только те, которые содержали 1 и 4. Я знаю, что моя скотина решение сила будет работать в O (2 ^п) времени, потому что математически ^{2 п} подмножеств и я должен перебрать их все.

Для моего рекурсивного решения. то, что я сделал, нарушило эту проблему, так что единственными решениями, которые были созданы/будут проверены, будут те, которые содержат 1 и 4. Например, с 1 вы можете перейти к 2,3,4, и если вы перейдете к 2, вы можете пойти до 3,4 и т. д. до 4.

После анализа обоих алгоритмов я понял, что единственное различие заключается в том, что деление и победа не будут проверять подмножества, у которых не было 1 и 4, но грубая сила, скажем, {2,3}. Как это различие повлияет на временную сложность рекурсивного алгоритма. Будет ли рекурсивный алгоритм также работать в O (2 ⁿ) или что-то меньшее, потому что он проверяет меньше подмножеств?

Answer 1

Дополнительный шаг для оптимизации в рекурсивном использовании memoization. Рассуждение идет - как только вы получите и остановитесь на посту x, он всегда будет стоить до конца, независимо от того, откуда вы пришли.
Получается, что все, что требуется, - это массив, держащий в индексе i самую низкую цену, чтобы добраться до конца. Это может быть заполнено справа налево в O (n²) времени.

Answer 2

Существует прямое решение динамического программирования.

Рассматривайте каждое более продолжительное оптимальное путешествие на каноэ как функцию более короткого оптимального путешествия на каноэ. Т.е., самый дешевый способ путешествовать на пост 4 - это самый дешевый способ путешествовать на должность 3 плюс лучшее решение для интервала с 3 по 4. Затем рассмотрите самый дешевый способ добраться до должности 5 в зависимости от того, как ранее рассчитывался самый дешевый способ посетить сообщение 4.

Реализовать эту рекурсию в коде и ваше решение должно быть O (N^2), похожая на многолетний КСПС любимец: стержень-винторезной проблема: http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

Дележа и властвуй подход будет проверьте синглтоны, на которых была начата сдача в аренду, а затем шаги «слияния» будут оптимизированы через новый doubleton/4ton/etc. Это будет намного лучше, чем O (2^n), потому что вы не будете перерасчитывать все возможности для каждого подпути, но это жадный алгоритм - он делает предположение о ответе, прежде чем у него будет отличная информация о ответе.

Если вы предполагаете, что оптимальное решение возникает во время некоторого шага слияния подмножеств, вам обязательно будут отсутствовать случаи, когда аренда лодки на 1 и возврат ее на n является наилучшим решением, но время выполнения - O (n log n). Но если вы проверите ввод и оптимизируете для каждого слияния, вы вернетесь к O (2^n).