「アルゴリズムとデータ構造」時間と空間の複雑さ

  [[361000]]

この記事はWeChatの公開アカウント「Unorthodox Front-end」から転載したもので、著者はUnorthodox Front-endです。この記事を転載する場合は、不適切なフロントエンド公開アカウントにご連絡ください。

序文

アルゴリズムを学ぶ意味があるのか​​と文句を言う人もいるかもしれません。せいぜい大企業の面接のときに使える程度です。大企業の面接アルゴリズムは、強い者と弱い者をふるい分けるための踏み石にすぎません。大企業の面接を受けるわけではないので、アルゴリズムを学ぶ必要はありません。本当にそうでしょうか。

絶対にそうではありません。コンピュータ業界では、フロントエンドであれバックエンドであれ、アルゴリズムは昇進の障害です。アルゴリズムがなければ、優秀なシニアエンジニアにはなれないと言えます。大企業に入社したいのであれば、アルゴリズムをある程度知っておく必要がありますが、それは面接のためだけではありません。私たちのプログラムと密接に関係しています。フロントエンドにはアルゴリズムは必要ないと言う人もいます。有名な仮想DOMはどこに置くのですか？それはアルゴリズムとデータ構造の現れです。誰かが「私は仮想DOMを書いていない」と言うかもしれません。 。 。そうですね、あなたは常にお金を稼ぎたいと思っており、技術的な道を選んで高給を得たいと考えています。アルゴリズムはその基礎です。

インターネットには、アルゴリズムのデータ構造を 7 日間で学習できる、アルゴリズムとデータ構造を 30 日間でマスターできるなどというアルゴリズムに関する記事やコースがたくさんあります。馬鹿げたことは言わないでください。アルゴリズムには近道はなく、少しずつ積み重ねていくしかありません。まず自分が天才ではないと信じること、次に毎日問題を解くことを主張することです。時間がない場合は、1 週間に 4 つか 5 つの問題を解くことができます。最適な速度は 1 日に 1 つの問題です。後期段階では、十分な時間がある場合や熟練している場合は、1 日に数問を解くこともできます。非常に頭のいい人でも、しばらくするとアルゴリズムを忘れてしまいます。したがって、重要なことは継続することです。

次に、アルゴリズムを一から学びましょう。アルゴリズムを一度も学んだことがない方は、この記事を読んで、アルゴリズムとは何か、データ構造とは何かを理解してください。アルゴリズムを勉強する一方で、自分の解決策が十分に優れているかどうかを確認する必要があります。良い解決策の判断は、時間と空間の2つの次元に反映されます。この記事では、これらを紹介することに焦点を当てます。これらはすべて、アルゴリズムを勉強する前に必要な知識です。アルゴリズムの旅に啓発をもたらすことができれば、それは素晴らしいことであり、大きな名誉です。すでにこの知識を知っている場合は、アルゴリズムの知識を広げることができるかどうかを確認するために、すぐに読んでみるのもいいでしょう。もちろん、間違いがあれば、ご指導いただければ、さらに光栄です。

データ構造とは

データ構造とは、実際にはプログラムがデータを保存および整理する方法です。データ構造は、特定の論理関係に従って整理された複数のデータ要素の組み合わせです。

データ構造は、プログラム内でデータを処理するための基本単位であり、プログラム全体で使用されます。

例えば、数字の1や文字のAはデータ構造です

たとえば、年、月、日の 3 つの形式で構成される 2020 年 12 月 14 日の日付もデータ構造です。

たとえば、配列 [1, 'a', '2020 年 12 月 14 日'] は、数字、文字、日付形式で構成されており、これもデータ構造です。

一般的に言えば、特定の形式のデータはデータ構造です。最も一般的なデータ構造は、文字列、配列、オブジェクト、ヒープ、スタック、リンク リスト、ツリー、ハッシュ テーブルなどです。これらのデータ構造の一部は理解できないかもしれませんが、心配しないでください。すぐに理解する必要はありません。フロント エンドには、私たちが好きでもあり嫌いでもある言語である JavaScript を使用します。この言語にはデータ構造がほとんどありません。そのため、リンク リストやツリーなどの構造は、オブジェクトを通じてシミュレートされます。まずこれを知っておく必要があります。

多くのプログラミングにおいて、データ構造の選択は基本的な設計上の考慮事項です。システム実装の難しさやシステム構築の品質は、最適なデータ構造が選択されるかどうかに大きく依存します。最適なデータ構造を選択すると、操作の効率が効果的に向上し、ストレージスペースの使用を節約できます。ただし、完璧なデータ構造は存在しないことに注意してください。各データ構造には利点だけでなく制限もあります。ニーズに応じて適切なデータ構造を選択する必要があります。

アルゴリズムとは何か

アルゴリズムとは何でしょうか？1+2+3=6であることは誰もが知っています。なぜ6になるのでしょうか？1+2は3、3を2つ足すと6になる、などとおっしゃるかもしれません。これは小学生でも知っている数学の常識です。広義のアルゴリズムです。

アルゴリズムとは、実際には問題を解決するための手順の完全な説明です。タスクを完了するための手順の正確かつ完全な説明を指します。

アルゴリズムの設計はデータ構造に依存することが多く、アルゴリズムの実装は採用されたデータ構造にさらに依存します。

問題を提案するためのアルゴリズムは、抽象的なものから具体的なものへのプロセスです。

• 問題を分析し、データ構造を選択し、予備的な解決策を考え出す
• 解決策を合理的に多くのステップに分割する
• 繰り返しステップに適切なループ変数を選択する
• プログラム実装に簡単に変換できる自然言語を使用してアルゴリズムを簡潔に記述する

アルゴリズムとは何かを理解した後、時間と空間の複雑さを見てみましょう。通常、さまざまなアルゴリズムの長所と短所は次の 2 つの側面から測定されます。

• 時間次元: コードの実行に要する時間、つまり時間計算量を指します。
• スペース次元: コードの実行によって消費されるスペース、つまりスペースの複雑さを指します。

次に、時間計算量と空間計算量を徐々に分析していきます。まずは時間計算量についてお話ししましょう。

時間計算量

時間の複雑さについて話す前に、まずコード実行回数という概念を理解する必要があります。これは、ステートメント頻度または時間頻度とも呼ばれ、T(n) で表されます。

例を使って段階的に説明しましょう。まず関数fn1を見てみましょう。

関数fn1(){
  console.log( "文の終わり" )
  コンソールログ( "isboyjc" )
 }

この関数内のステートメントが何回実行されるかを見てみましょう

明らかに、この関数にはconsole.log("end of sentence")とconsole.log("isboyjc")の2つのステートメントしかないので、この関数のコードが実行される回数は2であると言えます。

関数fn2をもう一度見てみましょう

関数fn2(n){
 ( i = 0; i < n; i++ とします){
    console.log( "文の終わり" )
  }
 }

まず関数 fn2 の実行可能ステートメントを見てみましょう。

 i = 0とする
私 < n
私は++
 console.log( "文の終わり" )

n = 3 と仮定し、それらを 1 つずつ挿入して、各実行ステートメントが実行される回数を確認します。

let i = 0 この文は最初のforループ宣言時に一度だけ実行される

i < n この文が実行される回数は、パラメータnの大きさに応じて異なります。n = 3、つまりi=0、i=1、i=2、i=3のときに実行されます。つまり、この文が実行される回数はn + 1回です。

i++ の実行回数は、パラメータ n のサイズによっても異なります。n = 3 の場合は、i = 0、i = 1、i = 2 のとき、つまり n 回実行されます。

console.log("文の終わり") このステートメントが実行される回数は、依然として仮パラメータ n のサイズに依存します。n = 3 の場合、3 回実行されるため、このステートメントは関数内で n 回実行されます。

 1 + (n + 1) + n + n = (3n + 2)

すると関数fn2は合計3n + 2回実行される。

コードが実行される合計回数は通常T(n)で表されます。したがって、上記のfn1/fn2関数が1回呼び出される合計回数は

T(n) = 2 // fn1
 T(n) = 3n + 2 // fn2

上記の n は問題の規模、つまり入力データのサイズまたは数を指します。T が関数自体で、n がパラメータであると単純に理解することもできます。

関数fn1はいずれの場合でも2回実行される

関数 fn2 の実行回数の合計は、n のサイズに応じて変化します。

考えてみましょう。コードが実行される合計回数を使用して実行速度を測定できるでしょうか?

答えはもちろんノーです。コードの行数が多い場合、実行回数を1行ずつ数えるのは面倒すぎます。例えば、関数内で関数を適用したり、ループ内でループを適用したりする場合、実行回数を正確に計算するのは非常に面倒です。

そのため、アルゴリズムでは、コード実行速度を表すために、一般的に T(n) の簡略化された推定値を使用します。通常、それを表すには、より大きな文字 O、つまり Big O 表記を使用します。推定値であるため、データ サイズが大きくなるにつれてコード実行時間が変化する傾向を表します。そのため、漸近的時間計算量、または略して時間計算量とも呼ばれます。

この概念を明確にした後、上記のfn1/fn2の2つの関数の例を使用して、時間計算量を計算することができます。

 //fn1
 T(n) = 2 
 
 // 関数2
 T(n) = 3n + 2

まず関数 fn1 を見てみましょう。関数 fn1 の総実行回数は 2 で、定数 (一定レベル) です。つまり、いつ実行されても、この関数の総実行回数は 2 で、不変の値です。したがって、これを時間計算量 O で表すと、1 と直接推定でき、つまり時間計算量は O(1) です。

関数 fn2 をもう一度見てみましょう。その実行時間 T(n) は 3n + 2 で、constant*n + constant です。ここでは、constant*n と + constant の 2 つの部分として完全に考えることができます。n が増加すると、前者のみが変化し、後者は変化しません。したがって、時間計算量を表すときは、後者の定数、つまり constant*n を無視できます。constant*n の定数を直接 1 と見なすか、この定数を係数として無視することもできます。そうすると、最終的に関数 fn2 の時間計算量は n、つまり O(n) であると結論付けることができます。

「追伸：誰かが先生に数学の知識を返したかもしれないので、説明します。」

「定数」: 定数は通常の値であり、単純に固定値として理解できます。

**係数:** 係数は代数式の単項式における数値因子を指します。たとえば、a = 1 * a の場合、その係数は 1 です。2b = 2 * b の場合、その係数は 2 です。

別の例を見てみましょう。次の多項式は関数 T(n) を表します。その時間計算量を求めます。

 T(n) = 10n^4 + 100n^2 + 1000

実際、多項式の場合、最高次の項、つまり n の最高次数だけを保持する必要があります。この例では、n の 4 乗を保持します。係数と定数は無視でき、最終的な時間計算量は O(n^4) です。

"結論は："

T(n)が定数の場合、時間計算量はO(1)、それ以外の場合は時間計算量はO(T(n)の最高次項を保持し、最高次項の係数を削除する)

次に、次のコード スニペットの時間計算量を判断するための例をいくつか見てみましょう。

「例1：」

関数fn01(){
  console.log( "これが何なのか見てください" )
  console.log( "これは出力です" )
  console.log( "ハハハ" )
  a = 1とする
返す​
}

上記の関数 fn01 には 1 つのステートメントのみがあり、変更なしで 5 回実行されます。時間計算量は O(1) で、これは一定の時間計算量です。

「例2:」

関数fn02(n){
 ( i = 0; i < n; i++ とします){
    console.log( "これは出力です🎓" )
  }
 }

上記のように、関数 fn02 は上記のテキストの例 fn2 と同じで、ループは 1 つであり、時間計算量は O(n) で、線形時間計算量です。

「例3:」

関数fn03(n){
 ( i = 0; i < n; i++ とします){
    console.log( "外側のループ" )
 (j = 0; j < n; j++)の場合{
      console.log( "内部ループ" )
    }
  }
 }

この質問は上記とは異なります。まず内側のループだけを見てみましょう。内側のループは約n回実行され、次に外側のループがn回実行されます。最終的に、n * n = n^2、つまり関数fn03の時間計算量はO(n^2)となり、2次の時間計算量となります。3層ループの場合、時間計算量はO(n^3)となり、3次の時間計算量となります。

ここから、コードの時間の複雑さは n の累乗であることがわかります。そのため、ループのネストが複数層にならないようにしてください。

「例4:」

次の関数fn04を見てみましょう

関数fn04(n){
 ( i = 0; i < n; i++ とします){
    console.log( "外側のループ" )
 (j = 0; j < n; j++)の場合{
      console.log( "内部ループ" )
    }
  } 
   
 ( i = 0; i < n; i++ とします){
    console.log( "ハハハ" )
  }
 }

この関数には二重ループと単一ループがあり、実行回数は約n^2 + nです。上で述べた最高次項の保持によると、関数fn04の時間計算量はO(n^2)です。

「例5:」

アルゴリズムには、上記の通常のループ以外にも確かに多くのループがあります。次のものを見てみましょう。

関数fn05(n){
 ( i = 0; i < n; i++ とします){
    console.log( "外側のループ" )
 (j = i; j < n; j++)の場合{
      console.log( "内部ループ" )
    }
  }
 }

実際、このような状況に遭遇したときは、直接持ち込んで試してみることでルールを知ることができます。

i = 0のとき、内側のループはn回実行される。

i = 1のとき、内側のループはn - 1回実行される。

i = 2のとき、内側のループはn - 2回実行される。

i = 3のとき、内側のループはn - 3回実行される。

この時点で、パターンを発見しました。i が 1 増加するたびに、内部ループの実行回数が 1 回少なくなるため、簡単です。

i = n - 2の場合、内側のループは2回実行される。

i = n - 1のとき、内側のループは1回実行される。

最後に、n 個の内部ループの実行時間を合計して、最終的な不正確な合計実行時間を取得します。

 T(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1

上で述べたように、これは等差数列です。はい、わかっています。追加します

2 番目の項から始まる数列の各項と前の項との差が同じ定数に等しい場合、この数列は等差数列と呼ばれ、この定数は等差数列の公差と呼ばれます。公差は通常、文字 d で表されます。

例えば、1,3,5,7,9...(2n-1) の場合、等差数列 S(n) の一般式は S(n) = S1 + (n-1) * d となり、最初の n 項と式は次のようになります。

 S(n) = n*S1 + n*(n - 1)*d/2 
 
 // または
 
 S(n) = n*(S1 + Sn)/2

このようにして、結果を計算できます。上記の数列では、公差 d は -1 です。これを式に代入します。2 番目の式は簡単なので、2 番目の式を使用します。計算結果は同じです。

 // n*(S1 + Sn)/2 
 
 n*(n + 1)/2 = (n^2 + n)/2 = (1/2)n^2 + (1/2)n

最終的に、(1/2)n^2 + (1/2)n が得られます。上記によれば、最高次の項を取り、係数を除去するため、時間の計算量は O(n^2) になります。

「例6：」

別の例を見てみましょう

関数fn06(n){
 ( i = 1; i < n; i *= 2とします){
    コンソールログ( "isboyjc" )
  }
 }

いつものように、読み方がわからない場合は、いくつかのパラメータを試してパターンを確認することができます。

ループ内の出力回数を観察するには、それぞれ n=2、n=4、n=8、n=16 を使用します。もちろん、コードを直接実行することもできます。プロセスは説明するほど多くはありません。結果を直接見てみましょう。

 n=2のとき、T(n)=1を1回印刷する
n=4のときは、T(n)=2を2回印刷する。
 n=8のときは、T(n)=3を3回印刷する。
 n=16のときは、T(n)=4を4回印刷する。

実行回数に影響を与える主な要因は、ループ ステートメントの i*=2 です。ループが繰り返されるたびに、i は自身の値の 2 倍になります。注意深く観察すると、規則的な結果が得られます。

 n=2のとき、T(n)=1 // 2^1 = 2を1回印刷する
n=4のときは、T(n)=2を2回印刷します // 2^2 = 4
 n=8 のとき、T(n)=3 を 3 回出力します // 2^3 = 8
 n=16のとき、T(n)=4を4回出力します // 2^4 = 16

上記の規則によれば、2^実行回数 = n、つまり2^T(n)=nであることは難しくありません。これを調整してT(n)を求めることができます。つまり、2を底とするnの対数、つまりT(n)=log_2 nです。

「追伸：数学をもう一度やり直さなければなりません」

「対数:」a^n=b、つまり a の n 乗が b に等しい場合、n の値を求めるには、便宜上、log_a b と記述します。これは、a を底とする b の対数で、a は底、b は実数、n は対数です。

ループ内の出力回数だけを観察し、実行回数をすべてカウントしないのはなぜかと疑問に思うかもしれません。理由は前述のとおりです。これらの固有の定数と係数は完全に無視できます。では、最後にもう一度試してみましょう。

中間出力はlog_2 n回で、i = 1は1回だけ実行され、i

「例7:」

最後に、例を挙げてみましょう。

関数fn07(n,m){
 ( i = 0; i < n; i++ とします){
    j < m の場合{
      console.log( "理解できましたか?" )
      j = j * 2
    }
  }
 }

上の図に示すように、この関数には内側のループと外側のループに対応する 2 つのパラメータがあります。まずは内側のループから始めましょう。見覚えがありますか? 実際、内側のループは、一方が for を使用し、もう一方が while を使用していることを除いて、前の質問の関数 fn06 のループと同じです。前の質問では、時間の計算量については説明しません。内側のループの時間計算量は O(log n) です。

上でも説明した外側のループをもう一度見てみましょう。外側のループのみの時間計算量はO(n)です。

2 つのループはネストされているため、乗算できます。したがって、関数 fn07 の時間計算量は O(n*log n) となり、線形対数時間計算量となります。

この関数の出力はわかりますか？

「タイプするのは面倒なので、写真を見てみましょう。」

私はインターネットで画像を見つけました（著作権を侵害している場合は削除してください）。そして、一般的な時間計算量曲線をより明確に示すためにチャートを使用しました。

上図に示すように、横軸は n です。n が増加すると、異なる時間計算量の操作数または実行時間が増加することがわかります。

一般的な時間計算量レベルは

• 定数レベルO(1)
• 対数レベル O(log n)
• 線形レベル O(n)
• 線形対数レベル O(n*log n)
• 正方形レベル O(n^2)
• 立方レベル O(n^3)
• K乗O(n^k)
• 指数関数 O(2^n)

上から下に行くほど、時間の複雑さが増し、実行効率が低下します。よく使用されるもののほとんどが上記のグラフに示されています。

したがって、プログラミングや問題解決においては、時間の複雑さが低い方法を使用するようにする必要があります。

以上が時間計算量についての説明です。一般的な時間計算量もリストアップしました。次に、空間計算量について見てみましょう。

空間の複雑さ

スペース複雑度は、実際には、アルゴリズムまたはコードが動作中に占有するストレージ スペースの量を表します。

上で時間の複雑さについて説明しましたので、空間の複雑さについて話すのはずっと簡単でしょう。

空間計算量は S(n) で、これも Big O 表記法で表されます。早速例を見てみましょう。

「例1:」

関数fn001(n){
 ( i = 0; i < n; i++ とします){
    console.log( "空間の複雑さ" )
  }
 }

まず、スペースの複雑さはストレージ スペースに関連していることはわかっていますが、ストレージ スペースを決定するものは何でしょうか。それは宣言された変数に違いありません。関数 fn001 の変数宣言を直接見てみましょう。i は 1 つだけなので、この関数は i が使用できるスペースのみを開きます。すると、スペースの複雑さ S(n) は O(1) になります。i は常に変化していると言うかもしれません。確かに変化していますが、どのように変化しても、i は依然として数値であり、占有されるスペースは同じです。

空間計算量は時間計算量と同じです。コード内で宣言された変数が定数であり、渡された値の変化に応じて変化しない場合、その空間計算量は O(1) です。

「例2:」

関数fn002(n){
  arr = [] とします
  while(n --){  
    arr.push(n)
  }
 }

この例では、配列を宣言します。配列にはさまざまなタイプのデータを格納できることはわかっています。ループでは、n のサイズに応じて要素を配列 arr にプッシュします。したがって、n のサイズによって、配列内の要素の数と占有するスペースが決まります。したがって、スペースの複雑さは S(n) = O(n) です。

「空間計算量の概要」

空間計算量では、一般的に他の例は必要ないので、2つの例だけを挙げます。空間計算量は通常、O(1)/O(n)/O(n^2) だけです。他の例はまれです。もちろん、存在します。時間計算量がわかれば、空間計算量も簡単に分析できるので、詳細には触れません。

空間計算量の分析に関しては、実際には宣言された変数から直接開始し、関数本体で宣言された変数が渡された値の変化に応じてどのように変化するかを分析できます。

また、ここでは再帰的な状況を挙げていません。再帰は、ロシアの入れ子人形のように、関数内の関数であることに注意してください。実際にはこれに問題があります。再帰関数では、再帰の各層で再帰スタックが開かれることがわかっています。各再帰によって生成された変数やその他のスペース消費は、再帰スタックに格納されます。これもスペースです。変数を宣言するかどうかに関係なく、再帰がある限り再帰スタックは存在します。言い換えると、再帰がある限り、最小のスペース計算量は基本的に O(n) です。したがって、反復を使用できる場合は再帰を使用しないようにしています。

時間対空間

冒頭で、アルゴリズムの効率は主に時間と空間の 2 つの次元から評価すると述べました。しかし、通常、アルゴリズムでは、時間と空間は魚と熊の手のようなものです。このとき、アルゴリズムの問​​題には、時間計算量が低いが空間計算量がわずかに高い解と、その逆の解の 2 つが存在する場合があります。

この時点で私たちは何をすべきでしょうか? よく考えてみると、開発では通常、スペースよりも時間を優先することがわかります。考えてみてください。プログラムの場合、ユーザーはメモリの使用量には関心がありませんが、プログラムが使用される際の実行速度には関心があります。さらに、スペースはディスクです。この段階では、ディスク容量を拡張するためにお金を費やすことができますが、時間の場合はそれほど簡単ではありません。したがって、相対的な状況によっては、スペースと時間を交換しても問題ありません。

空間を時間と交換することは可能ですが、単に空間を時間と交換することはできません。2 つの次元の複雑さを可能な限り減らす必要があります。いくつかの矛盾する状況では、空間を時間と交換できます。

アルゴリズムを練習するときは、単に練習するだけでは十分ではありません。ソリューションの時間と空間の複雑さを分析する必要もあります。複数のソリューションの複雑さを分析し、それらを比較して最適なソリューションを見つけることができます。

面接中に、面接官がアルゴリズムの問​​題を出し、あなたが複数の解法を知​​っている場合、冷静なふりをして「時間と空間のどちらが好きですか?」と尋ねることができます。私はそれらすべてを解くことができますが、その後、面接官はあなたにそれらをすべて書き留めるように求めますか?

冗談です。面接の際には、複数の解決策を書き留めて、その解決策の時間的および空間的複雑さの違いを面接官に説明してみてください。なんと言えばいいでしょうか。素晴らしいですね。

やっと

この記事では、アルゴリズムの理論的基礎をいくつか紹介します。理解した後、問題を練習することができます。データ構造の種類に応じて、毎日1問練習することをお勧めします。仕事に飽きたときに問題を練習することをお勧めします。仕事で怠けるよりも、アルゴリズムを練習したほうがよいでしょう。害はありません。毎日問題を練習し続けてください。さあ。

GitHubはアルゴリズムの質問/テキスト/ビデオのソリューションをゼロから提供するアルゴリズムリポジトリを構築しました。一緒に学びましょう。GitHubポータル[1]

各質問のアルゴリズムのビデオ版を録画しました。主に文章で説明するために作成しました。説明が下手な場合があります。ビデオの詳細については、Bステーション[2]のリンクを参照してください。

これを見て、トリプルコネクトをしてみましょう。間違いがあれば、修正してください。また、公開アカウント「Unorthodox Front-end」をフォローして、アルゴリズムグループの友達とチームを組んで、効率を高めるためにアルゴリズムを磨くことも歓迎します。

参照

[1]GitHubリンク:

https://github.com/isboyjc/DailyAlgorithms

[2]ビリビリポータル：

https://www.bilibili.com/video/BV1T5411p7oN