0

特定の列で最大値を持つテーブルの行を見つけることができる、実装が簡単なアルゴリズムを探しています。次に、その特定の列の最大値に近い値を持つすべての行を見つける必要があります (これら 2 つのステップを組み合わせることができますか?)。次に、選択した行の中から、別の列で最小値を持つ行を見つける必要があります。

おまけ: そのようなエントリが複数ある場合は、別の列で最小値を持つ行を見つける必要があります。

はい、SQL(ite) でこれを簡単に実行できることは承知していますが、テキスト ファイルからデータベース テーブルにデータを解析するのに時間を無駄にしたくありません...

これを行う方法に関する単純なアイデアに興味があります (疑似コードで問題ありません)。現在、次の行に沿ってかなり複雑なものしか考えられません。

  • すべての行を反復して最大値を見つける
  • すべての行を反復し、リストの最大値に「近い」行を挿入します
  • 行の新しいリストで最小値を見つける
4

2 に答える 2

1

実際、あなたは正しいことをしています。行の値が既に並べ替えられていない限り、ステップ 1 ですべての値を調べることは避けられないためO(R)、そこで時間を費やすことになりRます。

2 番目のステップでは、そのコストもO(R)アルゴリズムの複雑さを低下させないようにするためのものです。

「最大値に近い」値の数が に関するものであると考える場合O(1)、R3 番目のステップはO(C)がC列の数です。最小値を見つけるためにすべての値をテストする必要があるため、値が並べ替えられていない場合、これ以上のことはできません。

あなたのアルゴリズムは、得られる最高の複雑さを持っています。

于 2012-11-01T18:44:09.723 に答える
0

これに対する私の見解：

  • その最初の列でテーブルを行ごとに並べ替えます
  • 最大値は、このソートされた列の最初または最後の値です
  • 近くにあるすべての値は、並べ替えられた列の最大値にできるだけ近い値です
  • それらの行を抽出します
  • 2 番目の列で再度並べ替えます
  • 上記と同じように最小値を見つけます...
  • そのようなエントリが複数ある場合は、3 番目の列でもう一度並べ替えます...

この速度は、使用するソート アルゴリズムによって決まります。

于 2012-11-01T18:49:22.847 に答える