TIL 20210308

今日、今日

時間複雑度

アルゴリズムアクセス法(greedy,Dynamic Programming)

今、今
時間の複雑さ
まず、アルゴリズムを簡単にご紹介します
アルゴリズムと資料構造は単純な機能のプログラムにおいて重要ではない.
しかし、思考力を養うための運動と考えられる.
時間の複雑さ.
アプリケーションの実行時間は、最小値、平均値、最大値に基づいて指標として表示されます.
時間複雑度のタグ

最長時間:大書き方

平均時間:Big-Setaマーキング法(Big-OとBig-OMegaの中値=>平均演算回数)

最小時間:大ω記号(最小演算量)

アルゴリズムを実行すると、
これはアルゴリズム内でデータ処理の時間に応じて最大,最小,平均に分ける方法である.
3つのマーキング法におけるBig‐ONotationに焦点を当てる.
最悪の場合を考慮すると,プログラミングは安全駆動と考えられる.
時間複雑度のサイズ
複雑な順序で区分され、O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(sqrt(x)) > O(logn) > O(1) n^2, n^3等の回数の変化等は無視する.データのサイズ(n)が十分大きいと無視できるからです.
logの底も同様の理由で無視されます.これは,演算回数によって大きな分割が行われるだけであるといえる.
時間の複雑さは、十分なデータを処理する際に有効です.
アルゴリズムメソッド
アルゴリズムは資料の処理方式を決定し,資料構造と密接に関連している.
今日見つかった2つの方法は,あまり資料構造形式を用いていないが,このデータを処理する方法論である.
欲張り
貪欲な選択方式は、全体の状況を小さな単位に分け、単位ごとに最も効率的な選択を行う方法です.
グリディの意味は貪欲で、アルゴリズムの方法も貪欲な選択についています.
全体を最小のケースに分け,そのケースで最も有効な選択を連続的に行い,所望の結果を導く.
次の機能があります.

貪欲選択属性(greedy choice property):すぐに最適な答えを選択します.

最適部分構造(最適サブ構造):部分の解決は全体の解決を表す.(再帰的に表すことができる)

グレースケールアルゴリズムの例
たとえば、
食後にデザートを選ぶ過程は以下のように定義されています.

私は最大5つのデザートがあります.

で選んだ種類のデザートは全部持って行きます.

デザートは以下の通りです.{과일:4, 아이스크림:1, 커피:1, 사탕:2}

一番スイーツを選ぶ方法

この問題を그리디に分解すると、まず最大順=>{과일:4, 사탕:2, 커피:1, 아이스크림:1}最初のデザートを選ぶ=>과일:4次に、選べるデザートを探します.=>커피 :1選択したデザートを返します.=>{과일 :4, 커피:1}特長
これは数が一番多いデザートを選ぶのに有効です.
最も多くの種類のデザートを選ぶ場合、状況はそうではありません.
一番種類の多いデザートを選ぶために、사탕(2), 커피(1), 아이스크림(1)が選択可能である(3가지).
最も多くのタイプを選択する必要がある場合、これは不適切な方法です.
ダイナミックプログラミング
全体の問題を小さなユニットに分けて考え、小さなユニットの問題を解決する方法を重ねて、全体の問題に近い方法で考えます.
動的計画法は最適な局所構造を持つ反復サブ問題(Overlapping Subproblems)をセグメント征服に分解する問題解決策である.
最も代表的な例はフィボナッチ数を求めるアルゴリズムである.

const fiboTop = (n, fibos = [0,1,1]) => {
  if(n <= 2) return fibos[n];
  fibos[n] = fiboTop(n-1, fibos) + fiboTop(n-2, fibos)
  return fibos[n];
} // top-down

const fiboBot = (n, fibos = []) => {
  if(n <= 2) return 1;
  
  for(let i = 3; i <= n; i++) {
      fibos[i] = fibos[i-1] + fibos[i-2]
  }
  return fibos[i]
} //bottom-up

fiboTop(n)関数は、n <= 2の区間で1を返します.
数字が大きくなるにつれて、n-1,n-2の入力結果が返されます.
最終的にn<=2の区間結果で計算された答えを再計算した.
私たちが望んでいるnのフィボナッチ数を見つけることができます.
memoization
現在のように結果を保存し、次の演算で結果値を保存すると、
この方法を用いると,再計算せずに実行に適用できる.
メモと呼ぶ.
明日、明日

明日の授業

早起き