T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS バイナリーサーチなど(2)

<<   作成日時 : 2016/01/13 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

ここで、やっとコンピュータサイエンスとプログラミング入門(Part2)を受講できるようになりました。約1.5か月遅れのスタートです。最後の授業が 1/15 配信なのですが、課題提出締切が 3/31 なので、未だ間に合います。しかし、1/中から gacco の講座が続々と開講されるので、ここで進めておかないと修了出来なくなります。。まあ、合格点が 80 点以上なので、修了しないことも十分あるんですが、、、

まず、バイナリーサーチのおさらいから
画像

リストとして、\(0〜9999999\) の整数が順番に並んでいるものを準備して、その中から \(-1\) を検索した結果を右に示してあります。このプログラムは前回に示したものとほぼ同じですが、検索の手数も右に出力しています。この場合 \(-1\) は該当リスト内には存在しないため、 \(23\) 回掛かっています。
\[
\log _{2}10^{7}= 7\log _{2}10\fallingdotseq7\times 3.32= 23.24
\]
と、つじつまが合いますね。

さて、バイナリーサーチはリストがソートされていることが前提です。
ソートされていない場合は順繰りサーチしなければいけません。
では、この「ソートされていない場合」に
 「順繰りサーチ」

 「データソート」+「バイナリーサーチ」
ではどちらが手数がかかるのか?
という問題がでてきます。
そうすると、話題はサーチ手順よりソート手順に向いていくことになります。
どうもソートは \(n\log _{2}n\) だけ手数が掛かるようなので、順繰りサーチのほうが手数が少ないようですね。

普通に考えるとリストを1回だけサーチするなんて現実的ではないでしょう。
もし、\(k\) 回サーチすることを考えると
 順繰りサーチ : \(kn\)
 データソート+バイナリーサーチ : \((n+k)\log _{2}n\)
となり、\(k\) が大きくなるとバイナリーサーチのほうが有利になるということですね。

さて、という訳で「選択ソート」を見ていくことにします。
画像

これは何をやっているんでしょうね?後記事でみていくことにします。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
バイナリーサーチなど(2) T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる