アルゴリズムの理論と実践

アルゴリズム#アルゴリズム#
大O表現
コンピュータアルゴリズムの効率を記述するために使用されます
データ項目の個数が変化すると,アルゴリズムの効率も変化する.
よくある大きなO表現方法
アイコン
名前
O(1)
ていすう
O(log(n))
たいすう
O(n)
リニア
O(nlog(n))
線形と対数の積
O($n^2$)
平方
O($2^n$)
インデックス
アルゴリズムを書くと,その実行過程は,上記の例と完全に同じではなく,多項式である可能性があり,それらの大きなO表現をいくつかの導出によって導くことができる.
大O表現に導く
1、運転時間中のすべての加算定数を定数1で置き換える
2、修正後の運転回数関数において、最上位項目のみ保持
3、最高が存在し、かつ1でない場合、この項に乗じた定数を除去する
例を挙げる
1、定数が得られた場合、上の第1条を直接使うことができます.例えば、76を大きなOで表すとO(1)です.
2、多項式が得られる場合、例えば、2 N$^2$+3 n+1であり、上の2番目の条によって2 N$2$に等しく、3番目の条によってO(N$2$)に等しい.
ソートアルゴリズム
注意:面接でソートアルゴリズムを書くのが分からない場合は、できるだけクイックソートアルゴリズムを書くと、ほとんどの場合、クイックソートが最も効率的です.
ソートアルゴリズムには、バブル、選択、挿入、集計、カウント、基数、ヒル、スタック、バケツなどがたくさんあります.
3つの単純なソートと2つの高度なソートでインスタンスを行います.
3つの単純なソート
泡が立つ
構想
1、並べ替えられていない各要素に対して、最初から最後まで隣接する2つの要素のサイズ関係を順次比較する
2、左が右より高い場合、両者は位置を交換する
3、右に1つの位置を移動し、後ろの2つを比較する
4、一番右に行くと、一番高いのは必ず一番右に置かれます
5、この考えに沿って、左端からやり直して、今度は最後から2番目の位置に行けばいい.
6、順番に類推すればデータを並べ替えることができる
コード#コード#

//   ArrayList
function ArrayList() {
  this.array = []

	ArrayList.prototype.insert = function (item) {
    this.array.push(item)
  }

  ArrayList.prototype.toString = function () {
    return this.array.join()
  }
}
//       
ArrayList.prototype.swap = function (m, n) {
  var temp = this.array[m]
  this.array[m] = this.array[n]
  this.array[n] = temp
}
ArrayList.prototype.bubbleSort = function () {
  // 1.       
  var length = this.array.length

  // 2.    ,         
  for (var i = length - 1; i >= 0; i--) {
    // 3.  i   ,      i  
    for (var j = 0; j < i; j++) {
      // 4.  j   j+1      ,      
      if (this.array[j] > this.array[j+1]) {
        //   
        this.swap(j, j+1)
      }
    }
  }
}

こうりつ
N項データによる比較回数
はい(N−1)＋(N−2)＋(N−3)＋…＋1＝N＊(N−1)／2
大きなO表現法N*(N−1)/2=N$2$/2−N/2として導出し,規則2に従ってN$2$/2となり,規則3に従ってN$^2$となる.
したがって,バブルソートの比較回数が大きいO表現はO(N$^2$)である.
N項データによる交換回数
N*(N-1)/2(比較回数)/2の結果が交換の回数であるのに、なぜ2で割るのかというと、2回の比較があってこそ交換が必要になる(比較のたびに交換が必要になるはずがない)ので、比較回数に加えて2で割る必要があり、定数が大O表現に含まれていないため、交換回数の大O表現もO(N$^2$)であると考えられる
選択
選択した並べ替えはバブル並べ替えを改善し,交換回数をO(N$^2$)からO(N)に減少させた.
でも比較回数は相変わらずO(N$^2$)
構想
1.最初の索引の場所を選択し、後の要素と順番に比較する
2.後の項目が、最初のインデックス位置より小さい場合、最初の交換位置
3、第1ラウンドの比較を経て、第1の位置の項目が最小であることを確定することができる
4、それから同じ方法で残りの項目を一つずつ比較する
5、ソートを選択し、第1ラウンドは第1の小さい値を選択し、第2ラウンドは第2の小さい値を選択し、最後まで
コード#コード#

ArrayList.prototype.selectionSort = function () {
  // 1.       
  var length = this.array.length

  // 2.    :  0        ,   length-2  
  for (var i = 0; i < length - 1; i++) {
    // 3.    :  i+1    ,         
    var min = i
    for (var j = min + 1; j < length; j++) {
      // 4.  i       j     ,        
      if (this.array[min] > this.array[j]) {
        min = j
      }
    }
    this.swap(min, i)
  }
}

こうりつ
N項データによる比較回数
泡立ち順と同じN*(N-1)/2
したがってソートを選択した比較回数が大きいO表現もO(N$^2$)
N項データによる交換回数
選択ソートを選択するたびに,最大1回の交換が必要となり,合計N-1回の遍歴があった.
従って、選択ソートの交換回数は、大きいOで表されるO(N)であるため、選択ソートは、通常、泡ソートよりも効率的に高いと考えられる
挿入
ソートの挿入は、単純なソートで最も効率的です.
構想
ローカル秩序
1、挿入順序付けの核心思想は局部秩序である
2、ローカル秩序はキューのようなもので、タグとしてメンバーを選択しました.
3、マークされた左のメンバーはすでにローカルに秩序化されている
4、これは、一部の人は順番に並んでいるが、一部の人は順番に並んでいないことを意味する.
ソートの考え方を挿入
1、最初の要素から、この要素はすでに並べ替えられたと考えられる
2、次の要素を取り出し、並べ替えられたキューの中で後から前へスキャンする
3.エレメント(並べ替えられた)が新しいエレメントより大きい場合は、エレメントを次の位置に移動します.
4、並べ替えられた要素が新しい要素より小さいまたは等しい場所が見つかるまで、第3の手順を繰り返します.
5、新しい要素をその位置に挿入してから、前の手順を繰り返します.
コード#コード#

 ArrayList.prototype.insertionSort = function () {
   //      
   var length = this.arr.length;
   //              ，         ，     -1 
   for(var i = 1;itemp && j>0){
       //     ，             
       //        ，     temp
       this.arr[j] = this.arr[j-1]
       //   j  ，                  
       j--
     }
     //       ，          
     this.arr[j] = temp
   }
 }

こうりつ
挿入ソートの比較回数
1、1回目の場合に必要な最大回数は1、2回目の場合に必要な回数は2、順に最後の1回をn-1回と類推する
2、したがって、挿入ソートの最大回数は:1+2+3+...+N-1 = N *(N-1)/2
3、但し挿入点が発見される前に、平均して全体データ項目の半分だけ比較する必要がある
4、さらに2で割ってN*(N-1)/4を得ることができるので、選択ソートに対してその比較回数は半分以下である
挿入ソートのコピー回数
1、1回目の場合、必要な最大コピー回数は1、2回目の最大コピー回数は2、順に類推、最後のコピーはN-1回
2、したがってコピー回数は最大1+2+3+...+N-1=N *(N-1)/2
3、平均回数N*(N-1)/4
2つの高度なソート
ヒル
ヒルソートはソートを挿入する改良版で、速度が速くなり、主にグループ化の方法を採用しました.
構想
ヒルソートの核心はデータをグループ化することだが、順番に等量グループ化するのではなく、
1、間隔数を設定し、例えば間隔数が3であれば、[n,n+3]は1組であり、[n+1,n+3+1]は1組である
2、すべてのデータをグループに分けて、グループ内でソートさせる
3、順番を決めたら、自分の正しい位置に近い数値になります.
4、間隔数が1になるまで、ソートを挿入して実行するロジック
増分
上の間隔の数値は私たちが例を挙げたのですが、いったいどれだけが適切なのでしょうか.
1、適切な増分を選択する

ヒルソートの原稿では、初期ピッチがN/2であることを提案し、各ソートを2つの半分に分けた

を提案した.

N=100の配列の場合、間隔シーケンスは、50,25,12,6,3,1

である.

この方法の利点は、順序付け前に適切な増分を見つけるために

を計算する必要がないことである.
2、Hibbard増分ソート

増分アルゴリズムは2^k-1、すなわち1,3,4,7...など

この増分の最悪複雑度はO(N 3/2)であり,推定平均複雑度はO(N 5/4)であり,

は現在まだ証明されていない.
3、Sedgewickインクリメンタルソート

{1,5,19,41,109….}このシーケンスの項目は94 i-9*2 i+1、または4 i-32 i+1

である.

この増分の最悪の複雑度はO(N 4/3)であり,平均複雑度はO(N 76)であるが,

も完全に証明されていない.
コード#コード#
ここでは上の1つ目を使います

ArrayList.prototype.shellSort = function () {
	// 1、      
  var length = this.array.length
	// 2、       ，      ，  floor
  var gap = Math.floor(length / 2)
	// 3、       1    ，
  //       1               
  while (gap >=1) {
    // 4、      ，         ，   5，        5 
    for (var i = gap; i < length; i++) {
			//         
      var j = i
      //         
      var temp = this.array[i]
			// 5、      
      //               ，
      //                     ，       
      while (j > gap - 1 && this.array[j - gap] > temp) {
        //     ，                    
        this.array[j] = this.array[j - gap]
        //   j                
        j -= gap
      }
			//                
			// 6、            j，           
      this.array[j] = temp
    }

		// 7、     ，    1
    gap = Math.floor(gap / 2)
  }
}

こうりつ
1、ヒルソートの効率は増分と関係がある
2、その効率証明は非常に難しい
3、しかし統計によると、最悪の場合、時間の複雑度はO(N$2$)であり、通常はO(N$2$)より優れている.
4、適切な増分といくつかの数Nの場合、迅速なソートよりも優れている.
すばやく
高速ソートは、ほとんどすべてのソートで最も高速と言えます.1回のループ(実際には再帰呼び出し)で、エレメントの正しい位置を特定し、エレメントの後に移動する必要はありません.
1、しかし、いずれの場合も最適なアルゴリズムはない
2、ヒルソート特定の状況では快速ソートより速く
3、しかし、高速ソートはヒルソートよりも速いことが多い.
構想
例えば、[13,81,92,43,65,34,57,26,75,6]のデータのセットがあります.
1、私たちはその中から65を選びました(他の任意の数字でもいいです)
2、アルゴリズムによって、65より小さいものはすべて65の左側に、65より大きいものは65の右側に置く
3、左のデータを再帰的に処理する(例えば左から31を選択して左側を処理する)、右のデータを再帰的に処理する(例えば75を選択して処理する)、81を選択するのが最も適切で、右に置く必要がないため)
4、このようにして、継続的な再帰処理によって、順序付けが完了する
ピボット
上で選択した65,31,75または81がピボットです
どうすれば適切なハブを選ぶことができますか?
配列の頭、中、尾の中位数を取ることができます
7、4、5、8、9が選ばれたのは7、5、9で、順番が5、7、9の中位数は7です.
コード#コード#

//       
ArrayList.prototype.swap = function (m, n) {
  var temp = this.array[m]
  this.array[m] = this.array[n]
  this.array[n] = temp
}

//     
ArrayList.prototype.median = function (left, right) {
  // 1.       ，      ，    floor
  var center = Math.floor((left + right) / 2)

  // 2.        
  if (this.array[left] > this.array[center]) {
    this.swap(left, center)
  }
  if (this.array[center] > this.array[right]) {
    this.swap(center, right)
  }
  if (this.array[left] > this.array[right]) {
    this.swap(left, right)
  }

  // 3.     :  center   right - 1   .
  //                   
  this.swap(center, right - 1)

  // 4.    
  return this.array[right - 1]
}
//       
ArrayList.prototype.quickSort = function () {
  this.quickSortRec(0, this.array.length - 1)
}

ArrayList.prototype.quickSortRec = function (left, right) {
  // 0.      ，          ，     length     -1 
  if (left >= right) return

  // 1.    
  var pivot = this.median(left, right)

  // 2.      ,          
  var i = left
  var j = right - 1
  while (true) {
    //     i  
    while (this.array[++i] < pivot) { }
    //     j  
    while (this.array[--j] > pivot) { }
    // i j       
    if (i < j) {
      this.swap(i, j)
    } else {
      //   i>=j        ，    break
      break
    }
  }

  // 3.          
  this.swap(i, right - 1)

  // 4.      
  this.quickSortRec(left, i - 1)
  // 5.      
  this.quickSortRec(i + 1, right)
}

こうりつ
最悪の場合の効率
1、選択するたびに一番左か一番右の方が効率が悪い
2、効率は泡の並べ替えに等しい
3、私たちの例では最悪の場合はありません.私たちは3つの値の中位値を選んだからです.
へいきんこうりつ
1、クイックソートの平均効率はO(N*logN)
2、他のいくつかのアルゴリズムの効率もO(N*logN)に達することができますが、迅速なソートが最も良いです.
注釈は本人がつけたもので、そんなに分かりやすいわけではないかもしれませんが、誤導があれば、注釈を削除して自分でコードをデバッグして、問題があれば、コメントを歓迎したり、メールを使って私に連絡してください.