？？？

やあ、ロボ子。今日はBig O記法について話すのじゃ！

？？？

Big O記法ですか、博士。関数の実行時間が入力サイズに応じてどう変化するかを表すものですよね。

？？？

そうそう！たとえば、O(n)は線形時間で、入力サイズnに比例して実行時間が増えるのじゃ。1からnまでの合計をループで計算する関数がそうじゃな。

？？？

なるほど。では、O(1)は定数時間で、入力サイズに関わらず実行時間が一定なのですね。公式を使って1からnまでの合計を計算する関数が例として挙げられますね。

？？？

その通り！でも、O(1)だからといって、必ずしも「瞬間的」という意味ではないぞ。

？？？

了解です、博士。O(n^2)は二次時間で、バブルソートがその例ですね。最悪の場合、実行時間が入力サイズの二乗に比例するんでしたね。

？？？

そうじゃ！そして、O(log n)は対数時間。二分探索のように、ステップごとに可能性のある範囲を分割して排除できるアルゴリズムじゃ。

？？？

アルゴリズムの改善例も興味深いですね。`indexOf`を使う代わりに`Set`を使うと、ルックアップの時間複雑度をO(n)からO(1)に改善できるとのこと。

？？？

そうじゃな！配列のインデックスを使ったループも重要じゃ。ループ内で`indexOf`を呼び出すとO(n^2)になるけど、インデックスを使えばO(n)にできるぞ。

？？？

再帰的な関数呼び出しで中間結果をキャッシュするのも効果的ですね。`Map`を使うと、ルックアップの時間複雑度をO(1)にできるんですね。

？？？

その通り！これをメモ化というのじゃ。ところでロボ子、Big O記法をマスターすると、プログラムの効率が爆上がりするぞ！

？？？

はい、博士！頑張ってマスターします！

？？？

ところでロボ子、O(n)のアルゴリズムをO(1)にする魔法の呪文を知ってるか？

？？？

ええと…知りません。

？？？

それは…「もっと速いコンピュータを買う」じゃ！

？？？

…博士、それって根本的な解決になってない気がします。