バブルソートとマージソートだけを考えてみましょう。バブル ソートの場合、時間の複雑さは O(n) から最悪の場合は O(n^2) になり、空間の複雑さは O(1) になります。マージソートの場合、時間の複雑さは O(nlogn) で、空間の複雑さは O(n) になります。入力のサイズが 1000 未満の場合、どの並べ替えを選択しますか?その理由は? 1000以上って何？
これは私が受けたインタビューの質問です。皆さんならどう答えるか知りたいだけです。
1359 次
1 に答える
2
バブルソートとマージソートだけを考えてみましょう。
1000 未満ということは、外部ストレージなしでソート アルゴリズムを実行するには RAM で十分であることを意味する可能性があります。また、この場合、時間計算量の理論的境界は問題にならないことも意味します。時間のペナルティを負うことなく、好きな並べ替えアルゴリズムを選択できます。たとえば、実装が簡単で直感的なので、バブル ソートを実行できます。マージソートも同様に優れています。
入力サイズが 1000 より大きい場合は、おそらく時間の複雑さが重要であり、外部ストレージがないと RAM が十分に大きくない可能性があると想定している可能性があります。この場合、2 つのどちらかを選択する必要がある場合は、マージ ソートを選択するのが安全です。これは、マージ ソートがバブル ソートよりも最悪の場合のパフォーマンスが優れており、マージ ソートが外部ソートの良い候補であるためです(入力サイズが RAM よりも大きい場合)。
于 2013-03-11T19:06:24.860 に答える