本当に知っておくべきアルゴリズムとデータ構造のトップ

12月 10, 2021admin

ソフトウェアエンジニアになりたいが、何から始めたらよいかわからない場合、それはアルゴリズムとデータ構造です。

一旦これらのプログラミングの柱の概要を理解すれば、どこでもそれらを見るようになります。

始めるにあたって、まず、検索とソートについて深く掘り下げましょう。

大まかに言って、すぐに知る必要のある検索アルゴリズムには、線形とバイナリという 2 つのカテゴリがあります。

線形探索

線形およびバイナリアルゴリズムは、探索される入力のサイズに基づいて、探索にかかる時間 (時間の複雑さ) を説明するためにそのように名付けられています。

たとえば、線形検索アルゴリズムでは、検索するアイテムが 100 個ある場合、最悪の場合、目的の値に行き当たる前に、入力のすべてのアイテムを調べる必要があります。検索にかかる時間が、検索項目の量と正確に相関しているため、線形と呼ばれます (100 項目/入力 = 100 チェック/複雑さ)

要するに、線形 = 単純 (アルゴリズムに巧妙さはない) ということです。たとえば、順不同で立っている人の列の中から友人の Lin を見つけようとしているところを想像してみてください。あなたはすでに Lin がどのような人か知っているので、Lin を認識するかしないかまで、一人ずつ順番に見ていけばよいだけです。それだけです。そうすることで、線形探索アルゴリズムに従っていることになります

バイナリ検索

バイナリ検索の名前の由来は、バイナリという単語が「2 つのものの、または 2 つに関連する」という意味で、アルゴリズムは、検索対象のアイテムを見つけるまで入力を 2 つの部分に分割して機能するためです。片方の半分には検索項目が含まれ、もう片方には含まれません。このプロセスは、入力が分割された場所が検索対象となる項目になるまで続けられます。二項探索は、基本的には消去法に対する高度に訓練されたアプローチに過ぎない。

このことをより明確にするために、ある例を挙げます。たとえば、左から右へ背の低い順に並んだ人々の一列の列から、友人の Bin (身長 155cm) を見つけようとしているとします。とても長い列で、全員の身長をBinの身長と比較しながら一人一人見ている時間はありません。

2 進法の入力になります。あなたは、列の一番真ん中にいる人を選択し、その人の身長を測定します。彼らは170cmです。ですから、すぐに、この人、およびその右隣の人は、Binではないことがわかります。問題が半分になったので、残りの列に目を向け、もう一度真ん中の人を選びます。身長は170センチ。そこで、その人とその左隣の人を除外して、問題を再び半分にします。という具合に。これを5、6回繰り返すと、林を見つけるのにかかった時間の何分の一かの時間で、すぐにビンにたどり着けるようになります。

並べ替え

項目のリストを並べ替えることは、開発者として行う最も一般的なプログラミングタスクの 1 つです。ここでは、最も便利なソートアルゴリズムの 2 つを見ていきます。

マージ

上記の例で順序付けられた人々の列に遭遇するのではなく、順序付けされていないグループから人々の順序付けられた列を作成する必要があるとしましょう。

まず、全員が身を寄せているグループを 2 つに分割します。

まず、全員が集まっているグループを二つに分け、その二つのグループをまた二つに分け、さらにその二つを繰り返して、完全に個人を相手にする。そして、その人たちをペアにして、背の高い人がもう一人の人の右側に立つようにします。

次に、順序付けられたペアを4つの順序付けられたグループに統合し、4つの順序付けられたグループを8つの順序付けられたグループに統合し、といった具合に、順序付けられたペアの統合を開始します。そして、最終的に、先ほどと同じような、高さ順の完全な人の列ができることに気づきます。あなたは知らず知らずのうちに、MergeSortのアルゴリズムに従って、この偉業を成し遂げていたのです。

QuickSort

QuickSort は少し複雑すぎて、人と一緒に簡単にイメージすることは困難です。では、もう少しコードに近づいてみましょう。

4 2 13 6 15 12 7 9

マージソートを使用することもできますが、クイックソートの方が一般的に高速だと聞いたので、それを試してみることにしました。最初のステップは、ピボットと呼ばれるリストの数字を選択することです。正しいピボット番号を選択することで、QuickSort の実行速度に大きな違いが生じます。

4 2 13 6 15 12 7 9

次のステップを簡単にするために、配列の先頭に区切り文字を作成し、それをポンド記号で表します。

# 4 2 13 6 15 12 7 9

配列の左から右へ移動しながら、ピボット (9) より小さい数字をセパレータの左に、ピボットより大きい (または等しい) 数字をセパレータの右に置くことが目標になります。配列の最初の数字から始めます。 4.

4 # 2 13 6 15 12 7 9

次の数字 2 でも同じことをします。

4 2 # 13 6 15 12 7 9

しかし、13 まで来ると、これはピボット番号 9 より大きく、すでにセパレータの右側に来ています。そこで、そのままにしておきます。次に、6 が出てきますが、これはセパレーターの左側に移動する必要があります。

4 2 # 6 13 15 12 7 9

次に、セパレータを移動して通過させます

4 2 6 # 13 15 12 7 9

次は 15 で、これはすでにセパレータの右にあるため、そのままにします。次に 12 です。同じことです。しかし、軸に到達する前の最後の数字である 7 は、6 と同じように移動の手助けが必要です。

4 2 6 # 7 15 12 13 9

それから、もう一度、セパレータを移動して通過させます。

4 2 6 7 # 15 12 13 9

そして、最後に、ピボット番号である 9 に到達します。

4 2 6 7 # 9 12 13 15

現在、9 の左にあるすべての数は 9 より小さく、9 の右にあるすべての数は 9 より大きいので、クイックソートの最初のサイクルは終了しました。次に、セパレータの両側にある4つの数値のセットをそれぞれ新しい配列として扱い、QuickSortを適用します。詳細は省きますが、次のラウンドでは4組の数値が得られるので、最後のQuickSortを簡単に適用することができます。最終結果は、次のような順序付きリストになり、より単純な MergeSort を使用した場合よりも生成にかかる時間が短くなります:

2 4 6 7 9 12 13 15

並び替えアルゴリズムチートシート

これらは、最も一般的な並び替えアルゴリズムとそれらをいつ使用するかの推奨事項です。これらを内面化してください! これらはどこでも使用されます。

ヒープソート。安定したソートを必要とせず、平均的なパフォーマンスよりも最悪の場合のパフォーマンスに関心がある場合。これは O(N log N) であることが保証されており、O(1) の補助領域を使用します。つまり、非常に大きな入力でヒープまたはスタック領域が予期せずに不足することはありません。これは、クイックソートの O(N²) 最悪ケースを回避するために、ある再帰深度の後にヒープソートに切り替わるクイックソートです。これは、O(N log N) パフォーマンスを保証しながら、クイックソートの平均的なケースを得ることができるので、古いクイックソートよりもほとんど常に優れています。おそらく、これの代わりにヒープソートを使用する唯一の理由は、O(log N) スタックスペースが実質的に重要である、メモリ制約の厳しいシステムにおいてです。 N が小さいことが保証されている場合、クイックソートやマージソートの基本ケースとして使用されます。これは O(N²) ですが、非常に小さな定数を持ち、安定したソートです。

バブルソート、選択ソート。何か素早く汚いことをしているときに、何らかの理由で標準ライブラリのソートアルゴリズムを使用できない場合です。挿入ソートに対するこれらの唯一の利点は、実装が若干簡単なことです。

クイックソート。安定したソートを必要とせず、平均的なケースのパフォーマンスが最悪のケースのパフォーマンスよりも重要な場合。クイックソートは、平均で O(N log N)、最悪の場合 O(N²) です。優れた実装では、再帰のためにスタック空間の形で O(log N) の補助ストレージを使用します。

マージソート。安定した O(N log N) ソートが必要な場合、これはほぼ唯一の選択肢です。唯一の欠点は、O(N) の補助領域を使用することと、クイックソートよりもわずかに大きな定数を持つことです。インプレースマージソートもありますが、AFAIKではそれらはすべて安定しないかO(N log N)より悪いものです。 O(N log N)のインプレースソートでさえ、古いマージソートよりもはるかに大きな定数を持つため、有用なアルゴリズムというよりも理論的な好奇心の対象になっています。