c++ - ソートアルゴリズムの再帰-常に悪いですか？

Question

マージソート、クイックソートは、おそらく最もよく知られているnlognソートアルゴリズムです。ほとんどの場合、それらの説明とc++コード例には再帰が含まれています。しかし、大量のデータになる再帰について理解している限り、スタックオーバーフローの大きなリスクがあります。では、実際には使用できないようなソートアルゴリズムに関する再帰の説明を無視するのは合理的ですか？

Answer 1

しかし、大量のデータになる再帰について理解している限り、スタックオーバーフローの大きなリスクがあります。

それはいくつかのことに依存します：

• 最近の末尾呼び出しはほとんど常に最適化されているため、再帰回数があっても、末尾再帰でスタックオーバーフローが発生することはありませんO(2^N)（アルゴリズムはまだ低速ですが、スタックがオーバーフローすることはありません）。
• ほとんどのソートアルゴリズムは、ダウンLog2(N)タイムを繰り返します。これは、ソートされるデータのテラバイトあたり最大40レベルになります。これは、メモリにテラバイトのデータを保持できるもののスタックをオーバーフローさせるのに十分ではありません。

実生活では使用できないようなソートアルゴリズムに関する再帰の説明を無視するのは合理的ですか？

いいえ、これらの説明を無視することは合理的ではありません。アルゴリズムが論理的に再帰的である場合、最良の説明も再帰的です。スタックオーバーフローを回避するために動的に割り当てられたスタックを使用するループでアルゴリズムを実装した場合でも、アルゴリズムの性質は再帰的なままであるため、何が起こっているかを理解する最良の方法は、再帰的な呼び出しが行われたふりをすることです。

Answer 2

O(n log n)並べ替えアルゴリズムでは、再帰的アルゴリズムによって発生するコールスタックの高さは通常（O(log n)再帰的反復ごとに問題サイズの比較的バランスの取れた分割を想定）です。

例外は、配列がすでに並べ替えられているときに常に最後の要素をピボットとして使用する単純な実装でのクイックソートの最悪のシナリオで発生します。この場合、O(n^2)実行時間があり、呼び出しスタックの高さが。になりO(n)ます。

（視覚化に役立つ場合：これは、BFSよりも少ないスペースを使用するDFSの背後にある理論的根拠にいくぶん類似しています-前者は一度に1つの「検索パス」のみを追跡しますが、後者はすべてを追跡します）。

Answer 3

O(n logn)アルゴリズムでは、通常、再帰のレベルを調べていますlog2(n)。

具体的な例を挙げるとlog2(1,000,000,000) = 30、スタックオーバーフローの大きなリスクはほとんどありません。

たとえば、再帰の深さが大きくなることが許可されている場合、問題が発生しますO(n)。スケーラブルなアルゴリズムは、これが起こらないようにする必要があります。

Answer 4

他の人が指摘しているように、スタックの深さは、再帰の最も深いレベルに等しく、通常は次数log（n）です。

再帰の「問題」は、通常、メソッド呼び出しの作成とパラメーターの受け渡しに伴うオーバーヘッドです。たとえば、階乗法を考えてみましょう

int factorial（int k）{if（k == 1）return 1 else return k * factorial（k-1）;}

これをn=21で呼び出すと、20回の乗算を実行しますが、20回のメソッド呼び出しを設定して返すというオーバーヘッドもあります。これははるかに多くの作業です。再帰的アルゴリズムを使用したい場合は、プライベートスタックを設定し、whileループを使用して、多くの（比較的高価な）メソッド呼び出しなしでアルゴリズムを実装できる場合があります。もちろん、改善（もしあれば）は言語固有です。