整数の行列の最大2次元サブセットを計算するアルゴリズムを作成するタスクが与えられました。-しかし、私はそのようなアルゴリズムのヘルプには興味がありませんが、これを解決できる可能性のある最良の最悪の場合の複雑さを知ることにもっと興味があります。
現在のアルゴリズムはO（n ^ 3）のようなものです。
私は、マトリックス内の要素を単純に合計することによって、マトリックスをいくつかのサブマトリックスに分割することによって、分割統治法のようなものを検討してきました。そしてそれにより、近似解を見つけるために考慮しなければならない行列の数を制限します。
最悪の場合（全数検索）は間違いなくO（n ^ 3）より悪くありません。これについては、Web上にいくつかの説明があります。
最良のケースははるかに優れている可能性があります：O（1）。すべての要素が負でない場合、答えは行列自体です。要素が正でない場合、答えはゼロに最も近い値を持つ要素です。
同様に、行列の端に正でない整数以外の行/列全体がある場合は、検索でこれらを切り落とすことができます。
私はそれを行うためのより良い方法はないと考えました。-少なくともまだ人間には知られていない。そして、主にその単純さのために、私が得た解決策に固執するつもりです。