4コマで勉強する基本情報処理

基本情報処理を4コマにしながら勉強中。 同じ勉強をしてる方々の参考の足しにでもなれば幸いです。

アルゴリズム

隣接行列

kihon120
今回はアルゴリズムでやってなかった部分があったので、臨時追加します。

一見、隣接行列を見ると何か暗号っぽくて、これがグラフとどう結びつくのかを悩んでしまいました。


けれど、仕組みを解いてみると、それほど難しいものではなくて
上でも話した第i行第j列と第j行第i列の要素が1のものが結ぶ枝と思えば簡単に解けました。

あと、このパタンは無向グラフと言って、右上と左下が対照になるのが特徴です。(よく見ると対象になってますよ)

なので上のグラフが矢印になると有向グラフになり、右上と左下が対照では無くなります。

あと上のは1と0の重みなしの無向グラフであり、重さが加わる重みつき無向グラフもあります。


あと、ブログ村ランキングに参加させて頂いています。
いろんなパワーに繋がるので、ちょっとだけクリック宜しくお願いします。
にほんブログ村 漫画ブログ 4コマ漫画へ にほんブログ村 資格ブログ 資格試験勉強法へ にほんブログ村 IT技術ブログ IT技術情報へ
最後に、いつも拝見・応援してくださる皆様どうもありがとうございます。

2分探索法&ハッシュ探索法

kihon111

アルゴリズムは今回で終わりとなりますが、彼女たちは今度はソフトウェアの方にて解説する予定です。


補足ですが2分探索法は2分の1にしながら探索していくので、昇順か降順に並んで無いと全く効果が出ません。
ポイントとしては探索回数が1回増えるとデータの個数が2倍になります。
なので、探索回数が2回増えるとデータの個数が4倍になります。


あと、ブログ村ランキングに参加させて頂いています。
いろんなパワー に繋がるので、ちょっとだけクリック宜しくお願いします。
にほんブログ村 漫画ブログ 4コマ

漫画へ にほんブログ村 資格ブ

ログ 資格試験勉強法へ にほんブログ村 IT技術ブログ IT技術情報

へ
最後に、いつも拝見・応援してくださる皆様どうもありがとうございま す。

線形探索法

kihon110
番兵さんはオチじゃなくて線形探索法の中に番兵法っていうものがあります。
要するに「ここが最後尾ですよ」という目印となるデータを用意して、そのデータを見つけた段階でデータはここで終了ってことを判断します。


ちなみに先頭から順番に探索するので、N個のデータの最大探索回数はそのまんまのN回となって平均は最初で見つける場合(1回)と最後に見つける場合(N回)の平均なので(1+N)/2となります。

ループ回数が1回なので計算量(オーダ)としてはO(N)です。

あと、ブログ村ランキングに参加させて頂いています。
いろんなパワーに繋がるので、ちょっとだけクリック宜しくお願いします。
にほんブログ村 漫画ブログ 4コマ漫画へ にほんブログ村 資格ブログ 資格試験勉強法へ にほんブログ村 IT技術ブログ IT技術情報へ
最後に、いつも拝見・応援してくださる皆様どうもありがとうございます。

整列アルゴリズム その2

kihon109
アルゴリズム、もう少しだけ続きますので、お付き合いを。


きっと、これだけだと分かりにくいのは重々承知ですが、
ポイントさえおさえれれば問題の方は何とか解けると思います。


ちなみに名称の方が違う呼び方になっている場合があるので
そこはしっかりとおさえた方が良いです。


シェルソートは改良挿入法、基本交換法はバブルソート、
基本選択法は選択ソート、基本挿入法は挿入ソートと言います。

あと問題でヒープ木を順序木と書いてある場合もあるので
ご注意ください。


あと、ブログ村ランキングに参加させて頂いています。
いろんなパワー に繋がるので、ちょっとだけクリック宜しくお願いします。
にほんブログ村 漫画ブログ 4コマ

漫画へ にほんブログ村 資格ブ

ログ 資格試験勉強法へ にほんブログ村 IT技術ブログ IT技術情報

へ
最後に、いつも拝見・応援してくださる皆様どうもありがとうございま す。

整列アルゴリズム その1

kihon108
厳密に言うと、基本挿入法の場合だけデータの並び順次第で
比較回数が異なる場合があります。


基本情報処理としてn(n-1)/2回で問題はありません。
って言うか、過去問で出ていますし。


あと計算量っていうオーダの単位でも表すことが出来ますが、
こちらは全部同じ、O(n2乗)となります。

このオーダっていうのは簡単に言うと大雑把に言うとこれぐらい
の計算量でしょ?という単位のようです。
あんまり問題でお目にかかる時が無いので深くは覚えなくても
いいかなと思います。


あと、ブログ村ランキングに参加させて頂いています。
いろんなパワー に繋がるので、ちょっとだけクリック宜しくお願いします。
にほんブログ村 漫画ブログ 4コマ

漫画へ にほんブログ村 資格ブ

ログ 資格試験勉強法へ にほんブログ村 IT技術ブログ IT技術情報

へ
最後に、いつも拝見・応援してくださる皆様どうもありがとうございま す。

プロフィール

ぺた@ぺん

タグクラウド
QRコード
QRコード
  • ライブドアブログ