4

私は明日非常に重要なインタビューのために勉強していますが、私が非常に問題を抱えていることが1つあります。それは、ソートアルゴリズムとBigOの効率です。

知っておくべき重要な数字は何ですか？最高、最悪、または平均の効率？

4

6 に答える 6

4

最悪、次に平均。いわゆる「隠し定数」の実際の影響にも注意してください。たとえば、古典的なクイックソートアルゴリズムは、最悪の場合はO（n ^ 2）であり、平均してO（n log n）ですが、マージソートは最悪の場合はO（n log n）ですが、実際にはクイックソートはマージソートよりも優れています。

于 2009-09-13T17:02:51.187 に答える
2

要するに。

並べ替えアルゴリズムの効率は、入力データとタスクによって異なります。

  • アーカイブ可能な最大速度のソートはn*log（n）です
  • データにソートされたサブデータが含まれている場合、最大速度はn * log（n）よりも優れている可能性があります
  • データが重複で構成されている場合、並べ替えはほぼ線形時間で実行できます
  • ほとんどの並べ替えアルゴリズムには用途があります

クイックソートバリアントのほとんどは、平均的なケースもn * log（n）ですが、通常、他のあまり最適化されていないアルゴリズムよりも高速です。安定していない場合は高速ですが、安定したバリアントはほんのわずかに遅くなります。主な問題は最悪の場合です。最高のカジュアルな修正はイントロソートです。

ほとんどのマージソートバリアントでは、最良、平均、および最悪のケースがn * log（n）に固定されています。安定していて、比較的簡単にスケールアップできます。ただし、アイテム全体のサイズに関連するバイナリツリー（またはそのエミュレーション）が必要です。主な問題はメモリです。最高のカジュアルな修正はティムソートです。

並べ替えアルゴリズムは、入力のサイズによっても異なります。私は、10Tサイズを超えるデータ入力では、マージソートバリアントに一致するものがないという初心者の主張をすることができます。

于 2009-09-13T18:27:45.683 に答える
2

もちろん、それらすべてを知ることは重要です。平均的な場合の1つのソートアルゴリズムの利点は、最悪の場合にひどい赤字になる可能性があることを理解する必要があります。最悪の場合はそれほど悪くはありませんが、最良の場合はそれほど良くはなく、ソートされていないデータなど。

于 2009-09-13T17:03:56.643 に答える
1

これらのファクトイドを単に覚えないことをお勧めします。彼らが何であるかを学びましょう。私があなたにインタビューしているなら、私はあなたがアルゴリズムを分析する方法を理解していることを示す質問をすることを忘れないでしょう。あなたがウェブページや本で見たものを吐き出すことができるだけではありません。また、面接の前日はこの勉強をする時間ではありません。

あなたの幸運をお祈りしています！！それがどのように進んだかコメントで報告してください！

于 2009-09-13T17:14:03.940 に答える
1

私はちょうど今私の大学での1セットのインタビューで終わりました...

すべてのアルゴリズムには利点があります。そうでなければ、存在しません。ですから、あなたが研究しているアルゴリズムで何がとても良いのかを理解する方が良いでしょう。どこでうまくいくのですか？どうすれば改善できますか？

これを行うときは、さまざまな効率の表記を自動的に読む必要があると思います。最悪のケースに注意し、平均的なケースに注意してください。最良のケースはまれです。

面接に最適です。

于 2009-09-14T16:33:57.997 に答える
0

また、特定の条件が存在する場合に使用できる他の種類の並べ替えを調べることもできます。たとえば、基数ソートについて考えてみます。http://en.wikipedia.org/wiki/Radix_sort

于 2009-09-14T01:00:51.887 に答える