16

これは、配列を並べ替えて、必要な条件が満たされるまで大きな数値を取得することで実行できることを私は知っています。それには少なくともnlog（n）のソート時間がかかります。

に改善はありますかnlog(n)？

すべての数値が正であると想定できます。

4

5 に答える 5

9

これがであるアルゴリズムですO(n + size(smallest subset) * log(n))。最小のサブセットが配列よりもはるかに小さい場合、これはになりますO(n)。

アルゴリズムの説明が不明確な場合は、 http：//en.wikipedia.org/wiki/Heap_%28data_structure%29をお読みください（詳細はわかりにくいですが、詳細はすべてそこにあります）。

  1. 配列を、最大の要素が時間内に利用できるように配置されたヒープに変換しますO(n)。
  2. 合計が十分に大きくなるまで、ヒープから最大の要素を繰り返し抽出します。これには時間がかかりますO(size(smallest subset) * log(n))。

これはほぼ間違いなく彼らが望んでいた答えですが、それが得られないことは取引を妨げるものではありません。

編集：これは、多くの場合高速ですが、低速になる可能性がある別のバリ​​アントです。

Walk through elements, until the sum of the first few exceeds S.  Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
    if min(in our heap) < element:
        insert element into heap
        increase current_sum by element
        while S + min(in our heap) < current_sum:
            current_sum -= min(in our heap)
            remove min from heap

ヒープを操作せずに配列の大部分を拒否するようになった場合、これは前のソリューションの最大2倍の速度になる可能性があります。ただし、配列の最後の要素がたまたまSより大きい場合など、速度が低下する可能性もあります。

于 2011-05-11T15:01:40.097 に答える
7

数値が整数であると仮定すると、通常のソートの複雑さを改善できます。n lg(n)この場合、値が0からSの間であるという追加情報があるためです（この場合、Sより大きい整数はSと同じです）。

値の範囲は有限であるため、鳩の巣ソートや基数ソートなどの非比較ソートアルゴリズムを使用して、 以下に進むことができますn lg(n)。

これらの方法はSの関数に依存しているため、Sが十分に大きくなる（そしてnが十分に小さいままである）場合は、比較ソートに戻す方がよい場合があります。

于 2011-05-11T12:18:22.610 に答える
6

これは、問題に対するO（n）の予想時間の解決策です。これはMoronのアイデアにいくぶん似ていますが、選択アルゴリズムが各ステップで行った作業を破棄せず、繰り返しのダブリングアプローチを使用するのではなく、潜在的に中央のアイテムから試行を開始します。

あるいは、残りの合計を保持する少しの追加の本を使用して、 実際にはクイックセレクトです。

まず、要素を並べ替えた順序で使用している場合は、目的の合計を超えるまで、最初に最大のアイテムを選択できることは明らかです。並べ替えが遅いため、注文情報が見つからないようにできる限り努力することを除けば、私たちのソリューションはそのようになります。

与えられた値がカットオフであるかどうかを判断できるようにする必要があります。その値とそれより大きいすべてのものを含めると、Sを満たすか超えますが、それを削除すると、Sを下回り、黄金色になります。

これが疑似コードです。エッジケースについてはテストしていませんが、これでアイデアがわかります。

def Solve(arr, s):
  # We could get rid of worse case O(n^2) behavior that basically never happens 
  # by selecting the median here deterministically, but in practice, the constant
  # factor on the algorithm will be much worse.
  p = random_element(arr)
  left_arr, right_arr = partition(arr, p)
  # assume p is in neither left_arr nor right_arr
  right_sum = sum(right_arr)
  if right_sum + p >= s:
    if right_sum < s:
      # solved it, p forms the cut off
      return len(right_arr) + 1    
    # took too much, at least we eliminated left_arr and p
    return Solve(right_arr, s) 
  else:
    # didn't take enough yet, include all elements from and eliminate right_arr and p
    return len(right_arr) + 1 + Solve(left_arr, s - right_sum - p)
于 2011-05-12T03:06:28.480 に答える
5

Theta（nlogn）に対して（漸近的に）改善できることの1つは、O（n log K）時間アルゴリズムを取得することです。ここで、Kは必要な最小要素数です。

したがって、Kが定数の場合、つまりlog nの場合、これは並べ替えよりも（漸近的に）優れています。もちろん、Kがn ^ epsilonの場合、これはTheta（n logn）よりも優れているわけではありません。

これを行う方法は、選択アルゴリズムを使用することです。これにより、O（n）時間でi番目に大きい要素を知ることができます。

次に、Kの二分探索を実行します。i= 1（最大）から開始し、各ターンでiなどを2倍にします。

i番目に大きいものを見つけ、i個の最大の要素の合計を見つけて、それがSより大きいかどうかを確認します。

このようにして、選択アルゴリズム（O（n））のO（log K）実行を実行し、合計実行時間はO（n log K）になります。

于 2011-05-11T14:51:21.010 に答える
0
  1. 数<Sを削除し、いくつかの数== Sが見つかった場合は、解決します
  2. 鳩の巣ソート番号<S

Sを超えるまで、ソートされた順序で要素の最高から最低までを合計します。

于 2011-05-15T05:19:53.363 に答える