アルゴリズム とは？

例えば整数が偶数か奇数か調べるなら、2で割った余りを求め、0なら偶数、それ以外なら奇数と返す手順だよ。図の13は余り1だから奇数。効率がよいものだけをアルゴリズムと呼ぶわけではないんだ。

そうだよ。先頭から順に見る線形探索と、並べ替え済みの配列で範囲を半分ずつ狭める二分探索は別の方法。二分探索には比較の順序がそろっている前提があり、並べ替えの手間は検索自体の回数と分けて考えるんだ。

O記法は、入力が大きくなるときの増え方を上から押さえる表記だよ。最悪時だけでなく平均時の評価にも使い、どの条件かを明記する。O(n)は正確にn回という意味ではなく、O(1)も必ず一瞬という意味ではない。定数倍などを省いた増え方の評価なんだ。

データが増えたときの時間やメモリを見積もり、手順やデータ構造を選ぶ手がかりになるよ。ただしO記法だけで小さなデータでの実測時間や使いやすさまで決まるわけではない。必要な処理と前提を整理し、実際の環境でも確かめるんだ。