まずは例題から
alist = [1,11,5,9,13,4,3,7]
このリストから13のインデックスを探すコードを考えてみてください。
今回は具体的なコードは書きませんが、おそらくforループで要素全体をインデックス0から調べる方法を考えたと思います。
この方法を使った時
最高の場合1つ目の要素で見つかり
最悪の場合8つ目の要素で見つかり
この方法を線形探索といいます。
その一方でリストを小さい数順に並び替えて二分探索という探索アルゴリズムを使うと。
二分探索は一回の操作でリストを2分割してターゲットを絞っていくので、
最高の場合1つ目の要素で見つかり
最悪の場合でも3つ目(8 = 2^3)の要素で見つかります。
二分探索を知らない方へ
[1,2,3,4,5]という小さい数順に並べられたリストで4を探したい時、リストの真ん中の3に最初着目します。4は3より大きいのでそれより左にある小さい数は調べる必要がありません。そして3と5 の間に着目すると4隣ターゲットと一致して探索終了となります。これが簡単な二分探索の説明です。
今回はたった8つの要素であったにもかかわらず調べる数が3倍近く変わることが確認できたと思います。
その上で実務的なコードではたくさんの要素がリストに入っています。よって、このかかる処理の差はますます変わります。
アルゴリズムの処理の回数の計算に使われるのがTime Complexity(時間計算量)の概念です。
要素をNとして、それにかかるアルゴリズムの複雑さを計算していきます。そのアルゴリズムの複雑さは実際にコードを実行してかかる時間と比例します。
例えば、
for i in alist:
print(i)
print("Done!")
Time Complexity N+1 = N
(なぜなら操作が一つ増えてもアルゴリズムの複雑さとしてはさほどかかわらないから)
Nの扱い方は数3のlim n→∞に似ています。
ちなみに二分探索のTime Complexityは対数(底2)なのでfor ループより断然早く処理できます。
少しでも皆様の参考になったら幸いです。