1

これは宿題です。

目標は、数値の配列を検索し（整数または> 0かどうかを指定しない）、任意の2つの数値の比率が特定のxに等しいかどうかを確認するアルゴリズムを擬似コードで提示することです。時間計算量はO（nlogn）未満でなければなりません。

私のアイデアは、配列（O（nlogn）時間）をマージソートしてから、|x|の場合にマージソートすることでした。> 1（バイナリトラバーサルアルゴリズムを使用して）降順ですべての番号のチェックを開始します。チェックには、各番号に対してO（logn）時間もかかる必要があり、最悪の場合、n回のチェックで合計O（nlogn）が得られます。私が何も見逃していない場合、これは、割り当てのパラメーター内で、O（nlogn）+ O（nlogn）= O（nlogn）の最悪のケースを与えるはずです。

ソート後に比率をチェックし始める場所はそれほど重要ではないことはわかっていますが、時間コストは1/2で償却されます。

私の論理は正しいですか？より高速なアルゴリズムはありますか？

明確でない場合の例：

与えられた配列{4、9、2、1、8、6}

2の比率で検索したい場合。

  1. マージソート{9、8、6、4、2、1}

  2. 与えられた比率は>1なので、左から右に検索します。

2a。最初の番号は9です。9/4>2をチェックします。9/6<2次の番号をチェックします。2b。2番目の数字は8です。8/4=2をチェックしています。完了

4

4 に答える 4

2

あなたが提示した分析は正しく、この問題を解決するための完全に良い方法です。ソートは時間O（n log n）で機能し、2n二分探索もO（n log n）時間かかります。とはいえ、ここでは「償却済み」という用語を使用したくないと思います。これは、別の種類の分析を指しているためです。

ソリューションを少し高速化する方法のヒントとして、ソリューションの一般的な考え方は、任意の数について、その数が配列に存在するかどうかを効率的に照会できるようにすることです。そうすれば、すべての数値をループして、比率が機能するものを探すことができます。ただし、高速アクセスをサポートするアレイの外部で補助データ構造を使用する場合は、メモリ使用量を増やすことを犠牲にして、ランタイムを短縮できる可能性があります。どのデータ構造が非常に高速なアクセス（たとえば、O（1）ルックアップ）をサポートしているかを考えてみて、ここでそれらのいずれかを使用できるかどうかを確認してください。

お役に立てれば！

于 2012-12-30T19:46:00.863 に答える
2

この問題を解決するには、O（nlgn）だけで十分です。

手順1、配列を並べ替えます。その費用はO（nlgn）

ステップ2、比率が存在するかどうかを確認します。このステップに必要なのはo（n）のみです。

u必要なのは2つのポインターです。1つは最初の要素（最小の要素）を指し、もう1つは最後の要素（最大の要素）を指します。

比率を計算します。

比率が指定された比率よりも大きい場合は、2番目のポインターを前の要素に移動します。

比率が指定された比率よりも小さい場合は、最初のポインターを次の要素に移動します。

上記の手順を次のように繰り返します。

  1. u正確な比率を見つける、または

  2. 最初のポインタが最後に到達するか、2番目のポイントが最初に到達します

于 2012-12-31T05:27:56.037 に答える
1

アルゴリズムの複雑さはO（n²）です。これは、配列を並べ替えた後、各要素を反復処理し（最大n回）、各反復で最大n -1分割を実行するためです。

代わりに、配列を並べ替えた後、各要素を反復処理し、各反復で要素を比率で除算して、結果が配列に含まれているかどうかを確認します。

  • 分割：O（1）
  • ソートされたリストで検索：O（log n）
  • 要素ごとに繰り返す：n回

時間計算量O（n log n）になります

あなたの例では：

  • 9/2 = 4.5（見つかりません）
  • 8/2 = 4（見つかった）
于 2012-12-30T19:49:05.813 に答える
1

（1）この配列のハッシュマップを作成します。時間コスト：O（n）

（2）すべての要素a [i]について、HashMapでa [i]*xを検索します。時間コスト：O（n）。

総費用：O（n）

于 2013-01-03T21:50:05.977 に答える