再帰と二分探索のアニメーション

関数 n = 速度

0 / 0

関数と n を選ぶと自動で構築されます。

fibdef fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

factdef fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

target = 配列サイズ速度

0 / 0

探索範囲

—

残り要素

—

最大ステップ ⌈log₂ n⌉

—

現在のステップ

—

target と配列サイズを設定してください。

→ ボタンか右矢印キーでステップを進められます。

binary_searchL, R = 0, len(a) - 1
while L <= R:
    M = (L + R) // 2
    if a[M] == target: return M
    elif a[M] < target:  L = M + 1
    else:                R = M - 1
return -1

配列サイズ速度

0 / 0

未処理未ソート（分割直後）ソート済み現在のステップ | 比較中使用済み今置いた配置済み

配列サイズを選んで「配列を作り直す」を押してください。

merge_sortdef merge_sort(a):
    if len(a) <= 1:               # ベースケース
        return a
    mid = len(a) // 2              # 分割
    L = merge_sort(a[:mid])        #   左半分を再帰的にソート
    R = merge_sort(a[mid:])        #   右半分を再帰的にソート
    return merge(L, R)             # 統治（マージ）

配列サイズ初期配置速度

0 / 0

未処理未ソートソート済み現在の呼び出し | ピボット（先頭）比較中小さい山へ大きい山へ定位置（確定）

配列サイズと初期配置を選んで「配列を作り直す」を押してください。

quick_sortdef quick_sort(A):
    if len(A) <= 1:
        return A
    pivot = A[0]                              # 先頭をピボットに
    less = [x for x in A[1:] if x <  pivot]   # 基準より小さい山
    more = [x for x in A[1:] if x >= pivot]   # 基準以上の山
    return quick_sort(less) + [pivot] + quick_sort(more)

アルゴリズム要素数速度

0 / 0

単純挿入ソート最良 — 平均 — 最悪 — 安定性 —

—

比較回数

交換・移動回数

要素数 n

—

現在のステップ

—

未処理比較中交換・移動注目要素 / pivot 最小候補 / 境界確定（整列済み）

アルゴリズムを選んでステップを進めてください。

insertion_sortfor i in 1 .. n-1:
    key = a[i]                 # 取り出す
    j = i - 1
    while j >= 0 and a[j] > key:  # 比較
        a[j+1] = a[j]          # 後ろへずらす
        j -= 1
    a[j+1] = key               # 挿入

bubble_sortfor i in 0 .. n-1:
    for j in 0 .. n-2-i:
        if a[j] > a[j+1]:        # 比較
            swap(a[j], a[j+1])   # 交換
    # a[n-1-i] が確定

selection_sortfor i in 0 .. n-1:
    m = i
    for j in i+1 .. n-1:
        if a[j] < a[m]: m = j    # 最小を探す
    swap(a[i], a[m])             # 先頭へ

merge_sortdef merge_sort(a, lo, hi):
    if lo >= hi: return
    mid = (lo + hi) // 2          # 分割
    merge_sort(a, lo, mid)
    merge_sort(a, mid+1, hi)
    merge(a, lo, mid, hi)         # 併合

quick_sortdef quick_sort(A):
    if len(A) <= 1: return A
    pivot = A[0]                              # 先頭をピボットに
    less = [x for x in A[1:] if x <  pivot]   # 基準より小さい山
    more = [x for x in A[1:] if x >= pivot]   # 基準以上の山
    return quick_sort(less) + [pivot] + quick_sort(more)

n = 速度

0 / 0

① 再帰木で数える：個数 × サイズ = n

—

▶ で再生、← → でコマ送り。各段の 個数×サイズ がいつも n になることを順に見せます。

② 仕事量を「面積」で見る — バブル vs マージ

バブル ≈ n² —

マージ ≈ n log₂ n —

横幅は同じ n、縦の高さがそれぞれ n（バブル）と log₂ n（マージ）。 n が大きくなるほどマージの縦が薄くなる。

③ 桁の差を見る（1 秒に 10⁸ 回計算できると仮定）

n	O(n²)：n(n−1)/2 回	O(n log n)：n⌈log₂ n⌉ 回	比 (n²/n log n)	n² の時間	n log n の時間

挿入する値（カンマ区切り、整数または単語）検索する値（カンマ区切り、空でも可）速度シナリオ

0 / 0

ノード数 n

—

高さ h

—

理想 ⌈log₂(n+1)⌉

—

現在の操作

—

比較回数

—

中順走査:

→ いつでも整列済みの列が取れる（BSTのルールの帰結）

ノード比較中訪れたノード（比較の履歴）新規挿入発見（検索成功）不在（検索失敗）部分木（クリックで切替）

挿入する値・検索する値を入力して「構築」を押してください。

insertdef insert(node, v):
    if node is None:                       # 空 → ここに新規
        return Node(v)
    if v == node.val: return node          # 重複は無視
    if v < node.val:                       # 小さい → 左へ
        node.left  = insert(node.left,  v)
    else:                                  # 大きい → 右へ
        node.right = insert(node.right, v)
    return node

searchdef search(node, v):
    if node is None: return False          # 見つからない
    if v == node.val: return True          # 見つかった
    if v < node.val:                       # 小さい → 左へ
        return search(node.left,  v)
    return search(node.right, v)           # 大きい → 右へ

挿入する値（同じ値を2つの順序で入れて比べる）左の順序右の順序検索する値速度

0 / 0

左：高さ h

—

左：比較回数

—

右：高さ h

—

右：比較回数

—

左：バラ順

右：昇順

同じ値を 2 つの順序で入れて、高さと比較回数の違いを体感する。

形（高さ）を決めるのは入れる順。中身は同じ。バランスよく入ると高さ ≈ log₂n、最悪は n−1（一直線＝連結リスト相当）。

値（カンマ区切り、整数または単語）シナリオ（⑦⑧と同じ事例）根まで持ち上げる節速度

0 / 0

根まで持ち上げる節

—

回転前の高さ

—

回転後の高さ

—

回転した回数

—

節持ち上げる節下ろす親持ち上がった後

中順走査:

→ 回転しても順序は不変（BSTのルールは保たれる）

値を入れて「構築」。持ち上げる節を選び ▶ 再生で「持ち上げて引っ張る」様子が動きます。

回転＝ある節を持ち上げ、親を反対側へ引き下ろす操作（左の子なら右回転・右の子なら左回転）。間にぶら下がる部分木は反対側の親へ付け替わる。並び順（中順走査）は不変。偏った所でこれを使うと木が低くなる ── それを自動でやるのが次の AVL木。

挿入する値（カンマ区切り、整数または単語）速度シナリオ（⑦⑧と同じ事例）

0 / 0

ノード数 n

—

AVL の高さ

—

素の BST なら高さ

—

回転した回数

—

現在の操作

—

節（下の数字＝BF）比較中たどった経路今入れた節偏りすぎ（|BF|≥2）持ち上げる節

中順走査:

→ 回転しても整列済みのまま

挿入する値を入れて「構築」。各挿入のあと、偏れば自動で回転して高さを保ちます。

AVL木＝挿入のたびに各節の BF（左の高さ − 右の高さ）を見て、|BF|≥2 になったら回転で直す木。おかげで昇順に入れても一直線にならず、高さは常に ≈ log₂n（＝検索・追加が O(log n)）。

① 再帰木で数える：個数 × サイズ = n

② 仕事量を「面積」で見る — バブル vs マージ

③ 桁の差を見る（1 秒に 10⁸ 回 計算できると仮定）

③ 桁の差を見る（1 秒に 10⁸ 回計算できると仮定）