線形探索 と 二分探索 横山 てつお 線形探索 最悪の比較回数 14 12 比較回数 10 8 6 4 2 0 0 5 10 15 20 サッカーボールの数 25 30 線形探索の改良 最悪の比較回数 14 12 比較回数 10 8 6 4 2 0 0 5 10 15 20 サッカーボールの数 25 30 二分探索 最悪の比較回数 14 12 比較回数 10 8 6 4 2 0 0 5 10 15 20 サッカーボールの数 25 30 例 • サッカーボールの数が 400 個のとき – 線形探索 400 回 – 二分探索 9 回 • サッカーボールの数が 800 個のとき – 線形探索 800 回 – 二分探索 10 回 (= 9 + 1) • サッカーボールの数が 40 億個のとき – 線形探索 40億回 – 二分探索 32 回 ディスカッション 1. 線形探索 vs 二分探索 それぞれどのような場合に使うべきか 2. 入力個数が n 個の場合は 線形探索 と 二分探索で それぞれ何回比較が必要か 3. 同じ計算をするが根本的に効率が異なる アルゴリズムは 他にどのようなものがあるか 画像の出典 • 天秤の画像 public domain http://freeillustrations.gatag.net/tag/%E5%A4%A9%E7%A7 %A4%E3%81%B0%E3%81%8B%E3%82%8A • サッカーボールの画像 public domain http://cc-library.net/010009536_freeillustraition/ • 分銅の画像 フリー http://sozaikoujou.com/19527
© Copyright 2024 ExpyDoc
