Java プログラミング スキル - データ構造とアルゴリズム「ソート アルゴリズムの分類と紹介」

導入

ソートとは、データのセットを指定された順序で並べるプロセスです。

分類カテゴリ

内部ソート: ソートのために処理する必要があるすべてのデータを内部メモリにロードすることを指します。一般的な内部ソートには、直接挿入ソート、シェル ソート、単純選択ソート、ヒープ ソート、バブル ソート、クイック ソート、マージ ソート、基数ソートなどがあります。

外部ソート: データの量がメモリにロードするには大きすぎるため、外部ストレージを使用してソートする必要があります。

アルゴリズムの時間計算量

プログラム (アルゴリズム) の実行時間を測定する方法は 2 つあります。

この方法は実行可能ですが、2 つの問題があります。1 つ目は、設計されたアルゴリズムの実行性能を評価するには、実際にプログラムを実行する必要があることです。2 つ目は、得られる時間の統計値は、コンピューターのハードウェアやソフトウェアなどの環境要因によって異なります。この方法は、どのアルゴリズムが高速かを比較するために、同じコンピューターで同じ状態で実行する必要があります。

事前推定法は、アルゴリズムの時間計算量を分析することで、どのアルゴリズムが優れているかを決定します。

時間周波数

アルゴリズムにかかる時間は、アルゴリズム内のステートメントが実行される回数に比例します。アルゴリズム内のステートメントが実行される回数が多いほど、時間がかかります。アルゴリズム内でステートメントが実行される回数は、ステートメント頻度または時間頻度と呼ばれます。これは、T(n) と表されます。

例えば、1から100までのすべての数字の合計を計算するには、2つのアルゴリズムがあります。

整数合計=0;
整数 終了=100;
 // forループ計算
( int i=1;i<= end ;i++) {
    合計+=i;
 }

実行回数は終了の長さによって決まります。T(n)=n+1 です。

 // 直接計算
合計 = (1+終了)*終了/2;

直接計算は一度だけ実行すればよく、そのT(n) = 1です。

時間頻度を見積もる際に注意すべき点:

• 定数項を無視する: たとえば、T(n)=2n+20 および T(n)=2n の場合、n が増加すると、20 は無視できます。
• 低次の項を無視します。たとえば、T(n)=2n^2+3n+10 および T(n)=2n^2 です。n が増加すると、3n+10 は無視できます。
• 係数を無視する: たとえば、T(n)=5n^2+7n および T(n)=3n^2+2n の場合、n が増加すると、5 と 3 は無視できます。

時間計算量

1. 一般に、アルゴリズムの基本演算文の繰り返し回数は、問題のサイズ n の関数であり、T(n) で表されます。n が無限大に近づくと、T(n)/f(n) の極限値が 0 でない定数になるような補助関数 f(n) がある場合、f(n) は T(n) と同じ大きさの関数と呼ばれます。これは、T(n)=O(f(n)) と表され、O(f(n)) はアルゴリズムの漸近的時間計算量、または単に時間計算量と呼ばれます。
2. T(n) は異なりますが、時間の計算量は同じである可能性があります。たとえば、T(n)=n^2+7n+6 と T(n)=3n^2+2n+2 の場合、T(n) は異なりますが、時間の計算量は O(n^2) です。
3. 時間計算量を計算する方法

• ランタイム内のすべての加算定数を定数 1 に置き換えます。
• 修正された実行カウント関数では、最高次の項のみが保持されます。
• 最高次の項の係数を削除します。

一般的な時間計算量

• 定数次数 O(1)

ループなどの複雑な構造がない限り、何行のコードが実行されても、このコードの複雑さはO(1)です。

整数i = 1;
整数j = 2;
 ++i;
 j++;
 m = i+j;整数i は、j の整数です。

上記のコードを実行すると、特定の変数の増加に応じて消費時間が増えることはありません。そのため、このタイプのコードがどれだけ長くても、数万行または数十万行であっても、その時間計算量は O(1) で表すことができます。

• 対数順序 O(log2n)

整数i = 1;
 (i<n){
  i = i*2;
 }

while ループでは、i は毎回 2 倍になります。乗算後、i は n にどんどん近づいていきます。x サイクル後に i が n より大きくなると仮定すると、この時点でループは終了します。つまり、2 の x 乗は n に等しくなり、x = log2n になります。つまり、ループが log2n 回実行されると、コードが終了します。したがって、時間計算量は O(log2n) です。

• 線形順序 O(n)

 (i=1;i<=n;i++)の場合{
  j = i;
  j++;
 }

for ループ内のコードは n 回実行されるため、消費時間は n の変化に応じて変化します。そのため、このタイプのコードでは時間計算量を O(n) を使用して表現できます。

• 線形対数順序 O(nlog2n)

 ( int m=1;m<n;m++)の場合{
  私 = 1;
  (i<n){
  i = i*2;
  }
 }

この線形対数順序 O(log2n) は、時間計算量 O(logn) のコードを N 回ループします。

• 平方順序 O(n^2)

つまり、2回のforループ、n*m

• 立方次数 O(n^3)

3層ループ

• K次 O(n^k)

k サイクル

• 指数順序 O(2^n)

一般的なアルゴリズムの計算時間は、小規模から大規模まで、O(1) です。

平均時間計算量と最悪時間計算量

1. 平均時間計算量とは、すべての可能な入力インスタンスが等しい確率で出現する場合のアルゴリズムの実行時間を指します。
2. 最悪の場合の複雑さは、最悪の時間複雑さと呼ばれます。一般的に議論される時間複雑さは、最悪の場合の時間複雑さです。その理由は、最悪の場合の時間複雑さは、アルゴリズムが任意の入力インスタンスで実行されるのにかかる時間の上限であり、アルゴリズムの実行時間が最悪の場合よりも長くならないことを保証するためです。
3. 平均時間計算量と最悪時間計算量が一致するかどうかは、アルゴリズムによって異なります (次の表を参照)。

アルゴリズムの空間計算量

1. 時間の計算量に関する議論と同様に、アルゴリズムの空間計算量は、アルゴリズムによって消費されるストレージ スペースとして定義され、これも問題のサイズ n の関数です。
2. 空間複雑度は、アルゴリズムが動作中に一時的に占有するストレージ スペースの量を測定するものです。一部のアルゴリズムが占有する必要がある一時的な作業単位の数は、解決する問題の規模 n に関係しています。n が大きくなると、スペース複雑度も大きくなります。n が大きい場合、クイック ソートやマージ ソートなど、より多くのストレージ ユニットが占有されます。
3. アルゴリズム分析を行う際、主に議論されるのは時間の複雑さです。ユーザー エクスペリエンスの観点からは、プログラム実行の速度の方が重要です。一部のキャッシュ製品 (Redis、Memcache) とアルゴリズム (基数ソート) は、基本的にスペースと時間を交換します。