テスト勉強--「データ構造とアルゴリズム」

ハレノ @hareno_t

……テストに備えてとりあえずまとめておこうか。勉強TLになります、ご容赦ください。

ハレノ @hareno_t

文字列照合……（代表例）単純照合、KMP法、BM法。 [データ構造とアルゴリズム]

ハレノ @hareno_t

KMP法……パターン列について、別の配列を用意する。その配列には、照合失敗した場合にその場所に一致させる配列番号を格納する。最悪O(n)。 [データ構造とアルゴリズム]

ハレノ @hareno_t

ex.パターン列："ABAAC",next="01110"（但しインデックスを１とする [データ構造とアルゴリズム]

雷鳴 @sorayukinoyume

@hareno_t 「私は大学生の時、一番難しいものはKMP法とコンパイラ原理と思います。」コンパイラ原理の先生はそう言いました

ハレノ @hareno_t

@sorayukinoyume KMP法……よく思いついたな、って思いますよ。

ミレトス＠煩悩黒子 @miretoss

@hareno_t BM法の方が頭いいと思うのは俺だけ？

ハレノ @hareno_t

@miretoss いや、無論BM法の方が効率も良いし、賢いやり方してると思うよ。うん。有効性もBM法の方が高いし、KMP法は必然的に思いつくようなものだし（アルゴリズムは難しいけれど）。

ミレトス＠煩悩黒子 @miretoss

@hareno_t 何か、KMP法の考え方は好きなんだけど、枕パターンって完璧じゃないと思うんだよね・・ある特殊な並べ方すると発見しない気がする

ハレノ @hareno_t

@miretoss というか、枕パターンが存在しない方が早く探索できる。 [データ構造とアルゴリズム]

ハレノ @hareno_t

BM法……ヒューリスティック１の場合のみが出題範囲。２は今回考慮しない。 [データ構造とアルゴリズム]

ハレノ @hareno_t

基本は「後ろから照合」する。一致しなかった場合、その文字列中に同じ文字が入っていなかったら、どれだけずらしても無駄足なので、一気に文字列文ずらす。それが可能であるような表を別に作る。 [データ構造とアルゴリズム]

ハレノ @hareno_t

処理時間はO(n/m)に近い。最悪O(n+m)。 [データ構造とアルゴリズム]

やまもと @ymtkyk

@hareno_t 割り算なら悪くない、データ量が増えると高速になるの？

ハレノ @hareno_t

@ymtkyk えーと、短い方の文字数がｍ、多い方の文字数がｎです。はい。

やまもと @ymtkyk

@hareno_t なーるほど、比で決まるってことか！

ハレノ @hareno_t

@ymtkyk そうですねー。Oはどちらかというと無限大への発散しやすさを表してるので、計算量自体は文字数が多くなればなるほど多くなりますが、それでもO(n^2)ほどは大きくならない、という意味です。 [データ構造とアルゴリズム]

ハレノ @hareno_t

KMP法って、三人寄れば文殊の知恵というのを実行してくれた良い例だよね（棒読み [データ構造とアルゴリズム]

ハレノ @hareno_t

教科書のP78の問題４．１が鬼畜。「Q:～～なのは何故でしょうか」「A:：本当の理由は不明である」 [データ構造とアルゴリズム]

@yurii09ch

@hareno_t 勉強会にいる3人全員が吹いた

ハレノ @hareno_t

@yurii09ch （。・ω・）ｂ

ハレノ @hareno_t

スタック……最後尾にプッシュ、最後尾からポップ。 待ち行列……最後尾にenqueue、前からdequeue。（なんかひｙ…… [データ構造とアルゴリズム]

ハレノ @hareno_t

最短経路問題：Dijkstra(ダイクストラ)アルゴリズムとFloydアルゴリズム。ダイクストラは一つ一つ追加していく。Floydは破壊的探索。 [データ構造とアルゴリズム]

ハレノ @hareno_t

データ整列法……単純洗濯法、単純挿入法、ヒープ整列法、クイックソート、バブルソート、シェル法、シェーカ整列法マージソート法etcetc... [データ構造とアルゴリズム]

ハレノ @hareno_t

データ探索法：線形探索、二分探索、ハッシュ法（複数通り）、B木を用いた探索。etcetc... [データ構造とアルゴリズム]