数学弱者なので対数やsumをうまく簡単な数式に変換することが出来ない｡(悲) 再帰木 部分問題の再帰呼び出しを木で図示しレベルごとのコスト､全体のコストを考えることができる 再帰木によるコストの推定→置き換え法によるコスト検証という流れでアルゴリズム…

アドホックで役に立たなさそうな気がする｡次の再帰木やマスター定理が本命か｡ 置き換え法 漸化式のコストを示すことが目的 substituion method 手順 1.解の形を推定する 数学的帰納法を用いて定数を求め､推定した解がうまく働くことを示す｡ 特徴 解の形が推…

CS勉強するのは割に合わないとかいってる舌の根も乾かぬうちにアルゴリズムを勉強していく回です。 分割統治 概要 分割:問題のサイズを分ける 統治:分けた問題を再帰的に解く 結合:部分問題を結合し元の問題の解を得る 直接解いた方が早い場合は直接問題を解…

tex on はてブを諦めない。 多項式 一般にで表される関数をnに関するd次の多項式という :多項式の係数(coefficient) ただし ※この制約はa_dが0のときn-1次の多項式になってしまうのを防ぐためにあるのだと思う。 である のとき、関数は多項式的に限定されて…

３章の内容。あまりアルゴリズム的な話題ではない。次回は分割統治。 昔はてなで読書会をやったみたいな記録があったので読んでます↓ https://motemen.hatenadiary.org/entry/20080828/1219893385 漸近記法 入力サイズが小さい時よりも、大きい時の増加率を…

アルゴリズムイントロダクションのメモ2 p24~35まで読了。練習問題は解かない。 マージソート 分割統治の典型的な例 分割:入力n長の列をn/2の部分列に分割 統治:部分列のソート 結合:マージ MERGE(A,p,q,r) A:配列 p,q,r:添字。ただしp<=q

kindleより達人出版会から買うのがおすすめ。 tatsu-zine.com とりあえず冒頭からp24まで読んだ。気になった用語などのメモ アルゴリズム:ある値または値の集合を入力として取り、ある値または値の集合を出力として生成する明確に定義された計算手続き(p4) …