データ構造とアルゴリズムの簡単な紹介

一般的なデータ構造にはどのようなものがありますか? 基本的な操作は何ですか? 一般的なソートアルゴリズムはどのように実装されていますか? それぞれの利点と欠点は何ですか? この記事では、アルゴリズムの基本、一般的なデータ構造、ソートアルゴリズムについて簡単に説明し、学生にデータ構造とアルゴリズムに関する基本的なレッスンを提供します。

1. はじめに

1 なぜアルゴリズムとデータ構造を学ぶ必要があるのでしょうか?

特定の問題を解決します。
プログラムパフォーマンスの徹底的な最適化の基盤。
思考方法を学びます: 現実世界の問題をコンピューター言語表現に変換する方法。

2 ビジネス開発はどの程度習得すべきでしょうか？

一般的なデータ構造とアルゴリズムを理解すれば、コミュニケーションの障壁はなくなります。

知識を柔軟に適用する: 問題が発生したときに、最適化するために使用するデータ構造とアルゴリズムを把握します。

2. データ構造の基礎

1 データ構造とは何ですか?

データ構造は、データの編成、管理、および保存形式であり、その目的は、データに効率的にアクセスして変更することです。

データ構造はアルゴリズムの基礎です。アルゴリズムが美しく機敏なダンサーに例えられるとすれば、データ構造はダンサーの足元の広大で堅牢なステージです。

2 物理構造と論理構造の違いは何ですか?

物理構造は、配列やリンクリストなど、人間の肉体や骨のように、目に見える形で、触れられる形で、現実のものです。

論理構造は人間の思考や精神のようなもので、キュー、スタック、ツリー、グラフなど目に見えず、実体がありません。

3 線形ストレージ構造と非線形ストレージ構造の違いは何ですか?

線形: スタックやキューなど、要素間の関係は 1 対 1 です。
非線形: 各要素は、ツリーやグラフなどの 0 個以上の要素に接続される場合があります。

3つのアルゴリズムの基礎

1 アルゴリズムとは何ですか?

数学: アルゴリズムは、特定の種類の問題を解決するために使用される公式とアイデアです。
コンピューター: 特定の計算および論理問題を解決するために設計された一連のプログラム命令。

2 アルゴリズムの品質を測定するにはどうすればよいでしょうか?

時間の複雑さ: 実行にかかる時間。
空間計算量: メモリサイズ。

3 時間計算量を計算するには?

Big O 表記法 (漸近的時間計算量): プログラムの相対実行時間関数 T(n) を n、n^2、logN などの大きさの順序に簡略化します。

時間計算量を導出するためのいくつかの原則:

実行時間が一定の大きさである場合は、定数 1 で表されます。
時間関数の最高次の項のみが保持されます。
最高次の項が存在する場合、その項の前の係数は省略されます。

時間計算量の比較: O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。

異なる時間計算量を持つアルゴリズムの実行回数の比較:

4 空間複雑度を計算するには?

定数スペース O(1): ストレージスペースのサイズは固定されており、入力サイズと直接関係はありません。

線形空間 O(n): 割り当てられた空間は線形集合であり、集合のサイズは入力サイズ n に比例します。

2次元空間 O(n^2): 割り当てられた空間は2次元配列セットであり、セットの長さと幅は入力サイズnに比例します。

再帰空間 O(logn): 再帰は特別なシナリオです。再帰コードには変数やコレクションの明示的な宣言はありませんが、コンピューターがプログラムを実行すると、「メソッド呼び出しスタック」を保存するための特別なメモリ領域が割り当てられます。再帰操作を実行するために必要なメモリ領域は、再帰の深さに比例します。

5. アルゴリズムの安定性をどのように定義するか?

安定: a が元々 b の前にあり、a=b の場合、ソート後も a は b の前にあります。

不安定: a が元々 b の前にあり、a=b の場合、ソート後に a が b の後に表示されることがあります。

6 一般的なアルゴリズムにはどのようなものがありますか?

まず、特定のアルゴリズムが特定の問題を解決することを理解することが重要です。

文字列: ブルートフォースマッチング、BM、KMP、Trie など。
検索: バイナリ検索、トラバーサル検索など
ソート: バブルソート、クイックソート、カウンティングソート、ヒープソートなど。
検索: TFIDF、PageRank など
クラスター分析: 期待最大化、k-意味、k-数字など。
ディープラーニング: ディープビリーフネットワーク、ディープ畳み込みニューラルネットワーク、生成的敵対ネットワークなど。
異常検出: k 近傍、ローカル異常係数など。
......

その中でも、文字列、検索、ソートのアルゴリズムが最も基本的なアルゴリズムです。

4つの一般的なデータ構造

1 配列

1) 配列とは何ですか?

データとは、同じ型の有限個の変数の順序付けられたセットです。配列内の各変数は要素と呼ばれます。

2) 配列の基本的な操作は何ですか?

読み取りO(1)、更新O(1)、挿入O(n)、削除O(n)、拡張O(n)。

2 リンクリスト

1) リンクリストとは何ですか?

リンクリストは、複数のノードで構成される、物理的に連続していない非連続的なデータ構造です。

単一リンクリストの各ノードは 2 つの部分で構成されます。1 つはデータを格納する変数 data で、もう 1 つは次のノードを指すポインタ next です。

2) リンクリストの基本的な操作は何ですか?

読み取りO(n)、更新O(1)、挿入O(1)、削除O(1)。

3) リンクリストと配列

配列: 読み取りが多く、挿入と削除が少ないシナリオに適しています。

リンクリスト: 挿入と削除が多く、読み取りが少ないシナリオに適しています。

3 スタック

1) スタックとは何ですか?

スタックは線形論理データ構造であり、スタックの要素は後入れ先出し方式のみで処理されます。最も古い要素が格納されている位置はスタックの一番下と呼ばれ、最新の要素が格納されている位置はスタックの一番上と呼ばれます。

類推すると、スタックは一方の端が閉じられ、もう一方の端が開いている中空のチューブであり、キューは両端が開いている中空のチューブです。

2) スタックを実装するにはどうすればいいですか?

配列の実装:

リンクリストの実装:

3) スタックの基本操作

プッシュO(1)、ポップO(1)。

4) スタックの用途は何ですか?

メソッド呼び出しスタックなどの履歴をバックトラックします。
ページのパンくずナビゲーション。

4 キュー

1) キューとは何ですか?

キューの要素が最後にのみ入力および終了できる線形論理データ構造。キューの出口側はキューの先頭と呼ばれ、キューの入口側はキューの末尾と呼ばれます。

2) キューを実装するにはどうすればいいですか?

配列の実装:

リンクリストの実装:

3) キューの基本的な操作は何ですか?

エンキューO(1)、デキューO(1)。

4) キューの応用

メッセージキュー
マルチスレッド待機キュー
ウェブクローラーがクロールする URL のキュー

5 ハッシュテーブル

1) ハッシュテーブルとは何ですか?

キーと値の間のマッピング関係を提供する論理データ構造。

2) ハッシュテーブルの基本的な操作は何ですか?

書き込み: O(1)、読み取り: O(1)、拡張 O(n)。

3) ハッシュ関数とは何ですか?

ハッシュテーブルは本質的に配列ですが、配列にはa[0] a[1] a[2] a[3]などの添え字に基づいてのみアクセスでき、ハッシュテーブルのキーは主に文字列型です。

ハッシュ関数を使用すると、文字列または他のタイプのキーを配列の添え字インデックスに変換できます。

長さ 8 の配列が与えられた場合、次のようになります。

キー=001121の場合、

インデックス = ハッシュコード ("001121") % 配列の長さ = 7

キー=thisの場合、

インデックス = HashCode ("this") % Array.length = 6

4) ハッシュ衝突とは何ですか?

ハッシュ関数によって異なるキーから得られる添字は同じになる場合があります。たとえば、キー 002936 に対応する配列の添字は 2 で、キー 002947 に対応する配列の添字も 2 です。これはハッシュの競合です。

5) ハッシュ衝突を解決するにはどうすればいいですか?

オープンアドレス指定方法: 例: Threadlocal。

リンクリスト方式: ハッシュマップの例。

6 木

1) 木とは何ですか?

ツリーは n (n ≥ 0) 個のノードの有限集合です。

n=0 のとき、それは空木と呼ばれます。空でないツリーには、次の特性が存在します。

ルートと呼ばれる特定のノードが 1 つだけ存在します。
n>1 の場合、残りのノードは m (m>0) 個の交差しない有限集合に分割でき、各集合はそれ自体がツリーであり、ルートのサブツリーと呼ばれます。

2) ツリートラバーサル?

（１）深さ優先

事前順序: ルートノード、左サブツリー、右サブツリー。

順番は、左のサブツリー、ルートノード、右のサブツリーです。

後順序: 左サブツリー、右サブツリー、ルートノード。

実装方法: 再帰またはスタック。

（２）幅優先

レイヤー順序: レイヤーごとに移動。

実装方法: キュー。

7 二分木

1) バイナリツリーとは何ですか?

二分木は木の特殊な形式です。名前が示すように、このツリーの各ノードには最大 2 つの子ノードがあります。子ノードは最大 2 つありますが、子ノードが 1 つしかない場合や、子ノードがまったくない場合もあります。

2) 完全二分木とは何ですか?

すべての非リーフノードに左と右の子があり、すべてのリーフノードが同じレベルにある場合、バイナリツリーは完全なバイナリツリーです。

3) 完全二分木とは何ですか?

n 個のノードを持つ二分木の場合、すべてのノードは階層順に 1 から n まで番号が付けられます。このツリーのすべてのノードが、同じ深さの完全な二分木内の 1 から n までの番号が付けられたノードと同じ位置にある場合、この二分木は完全な二分木です。

8 二分探索木

1) 二分探索木とは何ですか?

バイナリ検索ツリーは、バイナリツリーに基づいて次の条件を追加します。

左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はルートノードの値よりも小さくなります。
右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値よりも大きくなります。
左と右のサブツリーもバイナリ検索ツリーです。

2) 二分探索木の機能は何ですか?

検索 ==》バイナリ検索。
ソート ==》順序どおりのトラバーサル。

3) バイナリツリーを実装するにはどうすればいいですか?

リンクリスト。
配列: 疎なバイナリツリーの場合、配列表現はスペースを大量に消費します。

9 バイナリヒープ

1) バイナリヒープとは何ですか?

バイナリヒープは特殊な完全バイナリツリーであり、最大ヒープと最小ヒープの 2 つのタイプに分けられます。

最大ヒープの親ノードの値は、その左と右の子ノードの値以上です。
最小ヒープの親ノードの値は、その左と右の子ノードの値以下です。

2) バイナリヒープの基本的な操作は何ですか?

（１）挿入：最後に挿入するとノードが上方に浮き上がります。

（２）削除：先頭ノードを削除し、末尾ノードを先頭に置いてシンクします。

（３）二分ヒープを構築します。二分木 ==> 二分ヒープ、すべての非リーフノードが順番に沈みます。

3) バイナリヒープを実装するにはどうすればいいですか?

配列：

5つの一般的なソートアルゴリズム

1 古典的なソートアルゴリズムのトップ10

2 バブルソート

1) アルゴリズムの説明

バブルソートは単純なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

2) 実装手順

隣接する要素を比較します。最初の値が 2 番目の値より大きい場合は、2 つを交換します。
隣接する要素の各ペアに対して同じ操作を実行します。最初のペアから始めて、最後のペアで終了します。最後の要素が最大の数値になるはずです。
最後の要素を除くすべての要素に対して上記の手順を繰り返します。
並べ替えが完了するまで、手順 1 ～ 3 を繰り返します。

3) メリットとデメリット

利点: 実装と理解が簡単です。
デメリット: 時間計算量は O(n^2) であり、ソートする要素が多い場合は効率が比較的低くなります。

4) 適用範囲

データは基本的に整然としており、データ量も少ないです。

5) シーンの最適化

（１）データがすでに整っているにもかかわらず、バブルの問題は続く

このソートのラウンドで要素が交換されない場合、isSorted は true となり、その後の無意味な繰り返しを回避するために大きなループが直接終了します。

（２）一部のデータはすでに整列しているが、次のラウンドで走査される。

順序付けられたデータと順序付けられていないデータ間の境界を記録して、順序付けられた部分を次のラウンドで走査する必要がないようにする。

（３）１つの要素だけが間違っているが、ソートの全ラウンドが必要である

カクテルソート: カクテルをシェイクするのと同じように、要素の比較と交換は双方向で行われます。

3 マージソート

1) アルゴリズムの説明

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。現在のシーケンスを再帰的に 2 つに分割し (分割)、要素の順序を維持しながら前の手順で取得したサブシーケンスを統合し (マージ)、最後に順序付けられたシーケンスを形成します。

2) 実装手順

画像出典: https://www.cnblogs.com/chengxiao/p/6194356.html

長さ n の入力シーケンスを長さ n/2 の 2 つのサブシーケンスに分割します。
これら 2 つのサブシーケンスに対してそれぞれマージソートが実行されます。
2 つのソートされたサブシーケンスを最終的なソートされたシーケンスにマージします。

3) メリットとデメリット

アドバンテージ：

パフォーマンスは良好かつ安定しており、時間計算量は O(nlogn) です。
安定したソート、より多くのシナリオに適用可能。

欠点:

非インプレースソート、高い空間複雑度。

4) 適用範囲

大量のデータがあり、ソートが安定していると予想されるシナリオ。

4 クイックソート

1) アルゴリズムの説明

クイックソートは分割統治戦略を使用して、シーケンスを小さいサブシーケンスと大きいサブシーケンスの 2 つのサブシーケンスに分割し、2 つのサブシーケンスを再帰的にソートして、最終的にシーケンス全体をソートします。

2) 実装手順

シーケンスから要素を選択することをピボットと呼びます。
基本値より小さいすべての要素が基本値の前に配置され、基本値より大きいすべての要素が基本値の後に配置されるようにシーケンスを並べ替えます (同じ数字をどちらの側にも配置できます)。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これをパーティション操作と呼びます。
基本値より小さい要素の部分シーケンスと基本値より大きい要素の部分シーケンスを再帰的にソートします。

3) メリットとデメリット

アドバンテージ：

パフォーマンスは良好で、最適な時間計算量は O(nlogn) であり、ほとんどのシナリオでパフォーマンスは最適に近くなります。
インプレースソートはマージソートよりも時間の計算量が少なくなります。

欠点:

いくつかのシナリオでは、最悪のソートパフォーマンスは O(n^2) になります。
ソートが不安定です。

4) 適用範囲

大量のデータがあり、安定したソートを必要としないシナリオ。

5) シーンの最適化

（１）基本要素が選択されるたびに、最大または最小の要素が選択される

最初の要素を選択する代わりに、ピボット要素をランダムに選択します。
3 数値中央値法では、3 つの数値をランダムに選択し、中央の数値を参照要素として採用します。

（２）シーケンスには大量の繰り返しデータが含まれている

基準値より大きい、小さい、または等しい。

（３）クイックソートの性能最適化

2 軸クイックソート: 2 つのベンチマーク番号、例: Arrays.sort() 。

5. ヒープソート

1) アルゴリズムの説明

ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。スタックは、完全な二分木を近似し、スタックの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。

2) 実装手順

ソートされるキーワードの初期シーケンス (R1、R2…Rn) は、初期の順序付けされていない領域である最大ヒープ内に構築されます。
ヒープの最上位要素R[1]を最後の要素R[n]と交換します。新しい順序なし領域（R1、R2、…Rn-1）と新しい順序付き領域（Rn）が得られ、R[1、2、…n-1] <= R[n]が満たされます。
交換後の新しいヒープ最上部R[1]はヒープの特性に違反する可能性があるため、現在の順序付けされていない領域（R1、R2、…Rn-1）を新しいヒープに合わせて調整し、R[1]を順序付けされていない領域の最後の要素と再度交換して、新しい順序付けされていない領域（R1、R2、…Rn-2）と新しい順序付けされた領域（Rn-1、Rn）を取得する必要があります。順序付けられた領域内の要素の数が n-1 になるまでこのプロセスを繰り返し、ソートプロセス全体が完了します。

3) メリットとデメリット

アドバンテージ：

パフォーマンスは良好で、時間計算量は O(nlogn) です。
時間計算量は比較的安定しています。
補助空間計算量はO(1)です。

欠点:

データが変更されると、ヒープのメンテナンスコストが高くなります。

4) 適用範囲

データ量が多く、データがストリーミング方式で入力されるシナリオ。

5) 実際の状況では、クイックソートがヒープソートよりも高速なのはなぜですか?

ヒープソートのプロセスから、最大ヒープが確立された後、ヒープの最上部の要素と最後の要素が交換され、最後の要素が最上部から適切な位置に沈むことがわかります。最下部の要素は比較的小さくなければならないため、沈むプロセス中に、ほとんど無効な比較が大量に実行されます。したがって、ヒープソートの複雑さはクイックソートと同じで、どちらも O(NlogN) ですが、ヒープソートの複雑さの定数係数は大きくなります。

6 カウントソート

1) アルゴリズムの説明

カウンティングソートは比較ベースのソートアルゴリズムではありません。その中心となるのは、入力データの値をキーに変換し、それを追加の配列スペースに格納することです。線形時間計算量を持つソート方法として、カウンティングソートでは、入力データが特定の範囲の整数である必要があります。

2) 実装手順

ソートする配列内の最大の要素を見つけます。
最大要素値 + 1 に等しい長さの配列 C を構築します。
順序付けられていない乱数シーケンスを走査し、各整数をその値に応じて対応する位置に配置し、対応する配列インデックス値に 1 を加算します。
配列Cを走査し、配列要素の添え字値を要素の値と同じ回数だけ出力します。

3) メリットとデメリット

アドバンテージ：

パフォーマンスは比較ソートよりもはるかに優れており、時間の計算量は O(n+k) です (k はシーケンスの最大値)。
安定したソート。

欠点:

適用範囲は比較的狭いです。

4) 適用範囲

シーケンスの要素は整数であり、これは k がそれほど大きくなく、シーケンスが比較的集中している場合に適用されます。

5) シーンの最適化

（１）数字が０から始まらないのでスペースが無駄になる

シーケンスの最小値はオフセットとして使用され、シーケンスの最大値 - 最小値 + 1 は統計配列の長さとして使用されます。

7 バケットソート

1) アルゴリズムの説明

バケットソートは、カウントソートのアップグレード版です。これは関数のマッピング関係を利用しますが、その効率の鍵はこのマッピング関数の決定にあります。実装の原則: 入力データが均一分布に従うと仮定して、データを有限数のバケットに分割し、各バケットを個別にソートします (別のソートアルゴリズムを使用することも、バケットソートを再帰的に使用し続けることもできます)。

2) 実装手順