【アルゴリズム】アルゴリズムを理解する（I）—アルゴリズムの時間計算量と空間計算量

[[407579]]

序文

大企業の秋季採用の先行スタートが始まっており、新卒採用の秋季大幅強化の警鐘が鳴らされている。これは、誰もが厳しい採用競争に挑まなければならないことを意味する。筆記試験や面接は就職活動において乗り越えなければならないハードルであり、アルゴリズムはほとんどの人にとって難しいハードルです。体系的な学習と理解、そして実践を通じてのみ克服することができます。

より多くの方にデータ構造とアルゴリズムを理解していただくために、新しいブログ投稿シリーズ「アルゴリズムを少し理解する」を開始します。皆様が辛い日々を乗り越えられることを願っています。私のアルゴリズム研究の能力には限界がありますが、皆さんがその本質を抽出し、そこから学んでいただければ幸いです。

アルゴリズムとは何か

アルゴリズムとは、データを操作し、プログラムの問題を解決するために使用される一連の方法のことです。

さまざまなアルゴリズムの長所と短所を測定する方法は 2 つあります。

事後統計的手法: 統計、監視、およびコンピュータタイマーを使用してさまざまなアルゴリズムの実行時間を比較することで、アルゴリズムの効率を判断できますが、非常に大きな制限があります。
事前分析推定法: コンピュータプログラムをコンパイルする前に、統計的手法に基づいてアルゴリズムを推定します。

たとえば、フィボナッチ数列のルールは次のようになります。数列は 3 番目の項から始まり、各項の値は前の 2 つの項の値の合計になります。つまり、0、1、1、2、3、5、8...です。

分析: フィボナッチ数列のパターンを観察すると、数列をアルゴリズムを使用して表現する場合、最初の 2 つの項と、3 番目の項から始まる要素の計算の 2 つのケースに分割する必要があることがわかります。

最も簡単な方法は、再帰を使用してフィボナッチ数列アルゴリズムを実装することです。

関数fib(num){
  if(num <= 1) numを返します。
 fib(num - 1) + fib(num - 2)を返します。
 }

もちろん、ループを使用してこれを実現することもできます。

関数fib(num){
  if(num <= 1) numを返します。
  num1 = 0、num2 = 1 とします。
 (i = 0; i < num - 1; i++)の場合{
    // 各追加は前の2つの項目の合計です
    合計をnum1 + num2とします。
    // 追加する前に、num2 が次の追加で num1 として使用されます。
    数値1 = 数値2;
    // 加算の結果は次のnum2として使用されます
    num2 =合計;
    // ただし、上記の2つのコードは交換できません
  }
 num2を返します。
 }

実際、高級プログラミング言語で書かれたプログラムがコンピューター上で実行されるのにかかる時間は、次の要因によって異なります。

アルゴリズムが使用する戦略と方法（アルゴリズムの品質）
コンパイルされたコードの品質（ソフトウェアのパフォーマンス）
問題の入力サイズ（必要な入力量）
マシンが命令を実行する速度（ハードウェア性能）

一般に、プログラムの実行時間は主にアルゴリズムの品質と問題の入力サイズによって決まります。

時間計算量と空間計算量

私たちは皆、ガウスの物語を学んだことがあります。主な内容は次のとおりです。ガウスが学生だったとき、先生は100以内のゼロ以外の自然数の合計を計算する方法、つまり1 + 2 + ... + 99 + 100 =を計算する方法を尋ねました。当時、多くの学生は最初から最後まで計算していましたが、ガウスは計算に忙しくなく、問題について考えていました。

ガウスは観察の結果、最初の項と最後の項の合計が 2 番目の項と最後から 2 番目の項の合計に等しく、101 になることを発見しました。また、他の項もこの規則に従うことも発見しました。全部で50組あるので、結果は101×50=5050となります。それで彼はクラスで最初に答えを計算した人になりました。

これは真実です。ナイフを研ぐことは木を切る作業を遅らせることはなく、正しい方法を使用すれば作業が容易になります。

それでは、ガウスアルゴリズムと従来のアルゴリズムの長所と短所を詳しく分析してみましょう。

従来のアルゴリズム:

関数commonFunc(){
  let sum = 0; // 1回実行
for (let i = 1; i <= 100; i++){ //n+1回実行
sum += i; //n回実行
  }
戻る  sum ; // 1回実行
}

ガウスアルゴリズム:

関数guassFunc(){
  let sum = 0; // 1回実行
sum = (1 * n) * n/2; // 1回実行
戻る  sum ; // 1回実行
}

上記のように、従来のアルゴリズムの実行回数は 2n+3 回であるのに対し、ガウスアルゴリズムの実行回数は 3 回です。最初と最後のステートメントの実行回数は同じなので、中間のアルゴリズムの主な焦点は n 回と 1 回の差です。ガウスアルゴリズムが従来のアルゴリズムよりはるかに優れていることは明らかです。

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

データ構造でアルゴリズムの時間計算量がどのように定義されているかを見てみましょう。

アルゴリズムの時間計算量: アルゴリズム分析を実行する場合、ステートメント実行の総数 T(n) は問題のサイズ n の関数であり、次に n による T(n) の変化が分析されて T(n) の大きさの順序が決定されます。アルゴリズムの時間計算量は、アルゴリズムの時間測定値であり、T(n)=O(f(n)) と表されます。これは、時間スケール n が増加すると、アルゴリズム実行時間の増加率が f(n) の増加率と同じになることを意味し、これはアルゴリズムの漸近的時間計算量、または略して時間計算量と呼ばれます。

翻訳してみましょう。時間計算量は、プログラムの実行時間を見積もるために使用される尺度です。アルゴリズムの問題サイズが n で、演算単位数 (プログラムが消費する時間を表すために使用される) が n であると仮定すると、データサイズ n が増加するにつれて、アルゴリズム実行時間の増加率は f(n) の増加率と同じになり、時間計算量 O(f(n)) と呼ばれます。

T(n)=O(f(n))

T(n)はコード実行時間を表す
nはデータのサイズを表す
f(n)は各コード行が実行される合計回数を表す。
Oはコード実行時間T(n)がT(n)に比例することを意味する。

上記の説明では、アルゴリズムの時間計算量を反映するために O() が言及されており、これはビッグ O メソッドとも呼ばれます。 Big O は上限を表すために使用されます。つまり、アルゴリズムの最悪ケース実行時間の上限、つまり最悪のケースで実行にかかる時間を表すために使用されます。

Big O メソッドの導出:

ランタイム内のすべての加算定数を定数1に置き換える
関数の実行回数の修正では、最高次の項のみが保持される。
最高次の項が存在し、それが1でない場合は、それに掛けられる定数を削除します。

次に、アルゴリズムの時間計算量の計算方法を次のように自分で練習してみましょう。

関数testFunc(n){
 for (let i = 0; i < n; i += i){ //1+log2(n)回実行する
for (let j = 0; j < n; j++){ //n+1回実行する
      console.log( "yichuan" ); // (1+log2(n))*(n+1) 回実行する
    }
  }
 }

最初の for ループでは、i+=i、つまり i=i+i=2i であることがわかります。したがって、2i=n のとき、n=log2(n) になります。ループから抜け出すには、1+log2(n) ステートメントを実行する必要があります。 2 番目の for ループでは、ループから抜け出す前にステートメントを n+1 回実行する必要があり、print ステートメントは (1+log2(n))*(n+1) 回実行されます。実際、big O 表記法を使用して加法定数と最高次の係数を無視すると、nlogn 回の実行が得られ、O(nlogn) として記録されます。

アルゴリズムの時間計算量を計算するときは、高次項の実際の状況に基づいて、加法定数、最高次項の係数、および対数項の底を無視できることを覚えておいてください。

一般的なカウント順序は次のとおりです。

一般的なアルゴリズムの時間計算量の順序を計算するのにかかる時間の比較を見ることができます。

さまざまな時間計算量曲線は次のとおりです。

アルゴリズム空間の複雑さ

実際、コードを書くときは、時間と引き換えにスペースを完全に犠牲にしていることになります。アルゴリズムの時間計算量と同様に、空間計算量はアルゴリズムのストレージスペースとデータサイズ間の増加関係を表します。

アルゴリズム空間の複雑さ: アルゴリズムに必要なストレージスペースを計算することで実現され、計算式は S(n)=O(f(n)) です。

nは問題の大きさを表す
f(n)は、ステートメント中のnが占める記憶領域の関数を表す。

関数spaceFunc(n){
  const arr = []; // コードの2行目
  arr.length = n; // コードの3行目
( i = 0; i < n; i++ とします){
    arr[i] = i * i;
  } 
   
 (j = n - 1; j >= 0; --j)の場合{  
    コンソールにログ出力します。
  }
 }

上記のコードを観察すると、次のことがわかります。コードの 2 行目では、変数 arr を格納するためのスペースがメモリ内に割り当てられ、空の配列が割り当てられます。コードの 3 行目では、配列の長さが n に設定され、配列には n undefined が自動的に入力されます。また、残りのコードはそれ以上のスペースを占有しないため、コード全体のスペース計算量は O(n) です。

最悪の場合と平均的な場合

最悪の実行時間は、プログラムの実行にかかる最大時間であり、これより悪いケースはありません。通常、実行時間について話すときは、最悪の場合の実行時間について言及しています。

平均ケース実行時間とは、プログラムが期待する平均時間を指しますが、実際のテストでは分析によって取得することが難しく、ある程度の実験データと推定が必要になります。

n 個の乱数の中から数字を検索する場合、最良のケースは最初の数字を検索して見つけることであり、時間の計算量は O(1) であることがわかっています。最悪のケースは、n 番目の数字を検索して見つけることです。したがって、数値を見つけるアルゴリズムの最悪の場合の時間計算量は O(n) であり、平均的な場合の時間計算量は O((1+n)/2)、つまり O(n/2) です。