3Sumの問題など、KSumの問題では、最初に配列をソートして最初の番号を選択する方法があります。次に、配列の残りの部分に対して2Sumを実行して、O（N^2）の実行時間を合計します。私は理解することが難しいと思う。私たちはN-2回について2Sumをしなければならないので、ランタイム全体は依然としてO（N^3）でなければなりません。私を教えてください。KSumはどのようにO（N^k-1）の実行時間を最小限に抑えますか？
仮定するT（N、K）はためKsum問題を計算するために必要な時間複雑度はサイズnの配列をソート表します。ベースケースは現在、他のすべてのkについて、我々は、配列を一度ループしなければならないし、K-1の合計が可能な場合のkのためにそう
T(n, 3) = n*T(n, 2)
T(n, 4) = n*T(n, 3)
....
T(n, k) = n*T(n, k-1)
ので、他の要素からチェック
T(n, 1) = n
T(n, 2) = n
です> 2時間の複雑さは、次のようになり
はO（n ^（K-1））
ありがとう！わかった。 –
@ J.Tang答えがあなたの問題に対処している場合は、受け入れ済みとマークしてください。 – meowgoesthedog
さて、あなたは小さなARのための2和を行いますあなたが別の数を選択するたびにX線を計算し、2-sumはすでにソートされているので最適化されます。これはO（n）よりも少し小さいためです。 – apokryfos
5つの合計問題では、あなたのアプローチによると、数字を選択して4sumを実行すると、数字を選択して3sumを実行するなど、 – marvel308
@apokryfos参照してください。私は2Sunについて混乱していたので、それが理由です。ありがとう！ –