2

上記の質問に対するアルゴリズムを探しているわけではありません。誰かに私の答えにコメントしてもらいたいだけです。

面接で次の質問をされました。

大量の数値セットから上位 100 の数値を取得する方法 (メモリに収まらない)

そして、これは私が言ったことです：

数値をそれぞれ 1000 のバッチで分割します。各バッチを "O(1)" 時間で並べ替えます。これまでの総所要時間は O(n) です。ここで、第 1 バッチと第 2 バッチ (O(1)) から最初の 100 個の数字を取得します。上記の計算された番号と 3 番目のバッチなどから最初の 100 を取得します。これには合計で O(n) が必要になるため、O(n) アルゴリズムになります。

インタビュアーは、1000 個の番号のバッチを分類すると答えます。O(1) 時間はかからないので、バッチから最初の 100 を選択することはありません。多くの議論の後、彼は O(n) 時間かかるアルゴリズムに問題はない、と彼は言いました。バッチの並べ替えには O(1) 時間がかかると言っている私の問題。

私の説明は、1000 は入力 (n) に依存しないということでした。n が何であるかに関係なく、私は常に 1000 個のバッチを作成します。計算する必要がある場合、ソートには O(1000*log 1000)) が必要です。これは本質的に O(1) です。

適当に計算するとこうなる

1000*log 1000 で 1 つのバッチを並べ替える (n/1000) そのようなバッチには 1000 * log 1000 * n/1000 = O(n*log(1000)) 時間 = O(n) 時間

私はこれについても多くの友人に尋ねましたが、彼らは私に同意しましたが、部分的には同意しました. ですから、私の推論が 100% 正しいかどうかは知りたくありません (99% 正しいとしても批判してください)。

この投稿は、上記の投稿された質問に対する回答を求めているわけではないことを覚えておいてください。1億の数字からトップ100の数字を取得するで、より良い答えをすでに見つけました

4

2 に答える 2

2

確かにそうですが、特にファイルシステムから各要素を2回[ソートで1回、第2フェーズで1回]読み取る必要があることをO(n)考えると、定数は非常に高く、ファイルシステムへのアクセスはメモリアクセスよりもはるかに遅くなります。これはおそらくアルゴリズムのボトルネックになるため、ソリューションはおそらくプライオリティ キューを使用する場合よりも2 倍遅くなります。

定数top 100の場合、素朴な解決策でさえ次のようになることに注意してくださいO(n)。

for each i in range(1,100):
   x <- find highest element
   remove x from the list
   append x to the solution

このソリューションもO(n)、100回の反復があるため、各反復でリストの2回のトラバーサルが必要です[いくつかの最適化により、反復ごとに1回のトラバーサルを実行できます]。したがって、トラバーサルの総数は 1000 よりも厳密に小さく、サイズに依存する要因はこれ以上ありません。したがって、解決策はO(n)- しかし、それは明らかにひどい解決策です。

インタビュアーはあなたの解決策を意味していたと思いますO(n)が、非常に大きな定数があります。

于 2012-04-16T07:18:47.767 に答える
2

インタビュアーは間違っていますが、その理由を考えると役に立ちます。あなたの言っていることは正しいですが、あなたが依存している明言されていない仮定があります。おそらく、インタビュアーは別の仮定をしています。

1000 個の数字の並べ替えが O(1) であると言うと、少し非公式になります。具体的には、N が無限大になる極限では、1000 個の数値をソートするコスト以上の定数があるということです。固定サイズのセットをソートするコストは N に依存しないため、制限も N に依存しません。したがって、N が無限大になると O(1) になります。

寛大な解釈は、インタビュアーがソートステップを別の方法で処理することを望んでいたということです. より正確に言えば、M が無限大になる (または必要に応じて M が N になる) ため、O(M*log(M)) であると言えます。M は数値のバッチのサイズを表します。N と M の両方が無限に近づくため、アプローチの全体的な O(N*log(M)) になります。もちろん、それはあなたが説明した制限ではありませんでした。

厳密に言えば、極限を明示せずに O(1) と言うのは無意味です。コンテキストから明らかなため、通常、アルゴリズムを気にする必要はありません。一般的に取られる制限は、単一のパラメーターが無限に近づくときです。N のみを考慮した場合の説明は正しいですが、N 以外を考慮することもできます。

于 2012-04-16T09:29:57.197 に答える