定義
O(√n)はデータ(N)の平方根分だけ確認すれば良いアルゴリズムです。
主な特性
- ✓面積(N)の代わりに一辺(√N)だけ確認
- ✓約数は常にペアがある
- ✓素数判定に非常に効率的
活用事例
こんな場面で使われます:
🛡️
素数判定
√nまで割り切れなければ素数
🔢
約数探し
36の約数: 1~6まで確認すれば対が自動で見つかる
📦
平方分割法
配列を√nブロックに分けて区間クエリを最適化
🔄
Mo's Algorithm
オフラインクエリ処理に√nを活用
計算量
時間計算量
最良
O(1)
平均
O(√n)
最悪
O(√n)
空間計算量
O(1)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始