最大部分配列 - ランタイム

Question

現在、ブルートフォースアルゴリズムと除算および征服アルゴリズム（再帰的）の両方について、maximum subarray problemを解析中です。

ブルートフォースアルゴリズムを使用すると、最悪の場合のランタイムはO（n^2）です。 再帰アルゴリズムを使用すると、最悪の場合の実行時間はO（n * log（n））です。

しかし、ブルートフォースは実際にはある一定の定数、例えばkまでの小さな入力に対してより速いので、kまでブルートフォースを使い、その後は再帰的に使うと考えました。

この解析方法、つまりパラメータnとkを使用して解析する方法がわかりません。 （O（k^2 *（n/k））= O（n * k）が必要なInsertion/Mergeソートにも同様の問題があります。

---

私は改正しようとして、theta表記を使用してみましょう。

"ブルートフォースが再帰的なk = 50まで高速である再帰的（ブルートフォースは再帰的（nとkをパラメータとして使用する））のブルートフォースを持つアルゴリズムの漸近的ランタイムは何ですか？"

パラメータnとkの両方を含める必要があります。また、これらの問題をテストするためには、これまでに再帰ツリーしかありません。

Answer 1

big-Oはアルゴリズムの長期的な成長率について話します。正式には、十分に大きいnに対して、ある関数の振る舞いはある定数の倍数よりも小さいと言います。これは、定数kの任意の選択肢を修正し、n ≤ kのO（n ）アルゴリズムとすべてのn> kのO（n log n）アルゴリズムを使用すると、全体のランタイムはO n log n）、nが十分に大きくなると、アルゴリズムの動作は純粋にO（n log n）アルゴリズムの振る舞いに依存するためです。

これは、dynamic programmingを使ってO（n）時間、O（1）空間でこの問題を解決し、配列を1回だけ通過させるアルゴリズムであるKadane's algorithmです。いずれのアプローチよりも（実際上または漸進的に）ほぼ確実に速くなるでしょう。

希望すると便利です。