Максимальный подмассив - время выполнения

Question

В настоящее время я анализирую проблему максимального подмассива как для алгоритма грубой силы, так и для алгоритма "разделяй и властвуй" (рекурсивный).

Используя алгоритм грубой силы,время выполнения в худшем случае - O (n ^ 2).При использовании рекурсивного алгоритма время выполнения в худшем случае составляет O (n * log (n)).

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

Я не уверен, как проанализировать это, то есть с помощью параметров n и k.(Существует аналогичная проблема для сортировки вставкой / слиянием, где требуется O (k ^ 2 * (n / k)) = O (n * k), поэтому я подумал, что могу использовать тот же результат, но ...).

---

Позвольте мне попытаться переформулировать и использовать тэта-нотацию.

"Каково асимптотическое время выполнения алгоритма с грубой силой внутри рекурсии (используйте n и k в качестве параметра),где грубая сила быстрее, чем рекурсивная, до k = 50. "

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

Answer 1

Помните, что big-O говорит о долгосрочной скорости роста алгоритма. Формально это говорит о том, что при достаточно большом n поведение одной функции меньше некоторого постоянного множителя другой. Это означает, что если вы исправите любой выбор константы k, а затем будете использовать алгоритм O (n ² ) для n & le; k и алгоритм O (n log n) для всех n> k, общее время выполнения будет O (n log n), поскольку при достаточно большом n поведение алгоритма зависит исключительно от поведения O (n log n) алгоритм.

Тем не менее, вы должны взглянуть на алгоритм Кадане , алгоритм, который использует динамическое программирование для решения этой проблемы за время O (n), пространство O (1) и просто один проход по массиву. Это почти наверняка будет быстрее (практически и асимпотически), чем любой из ваших подходов.

Надеюсь, это поможет!