#!/usr/bin/env python3
"""
Big-O 記法の定義を数値的に検証するプログラム。
f(n) = 3n² + 5n + 2 が O(n²) であることを確認する。
"""
 
 
def f(n: int) -> int:
    """解析対象の関数 f(n) = 3n² + 5n + 2"""
    return 3 * n * n + 5 * n + 2
 
 
def g(n: int) -> int:
    """上界を与える関数 g(n) = n²"""
    return n * n
 
 
def verify_big_o(c: float, n0: int, upper: int = 1000) -> bool:
    """
    f(n) ≤ c * g(n) が全ての n ≥ n₀ で成り立つかを検証する。
 
    なぜ数値的検証が有用か:
    - 証明の前に仮説を立てるための直感を得られる
    - 証明で選んだ c, n₀ が妥当かどうかを確認できる
    - 教育目的で定義を具体的に理解できる
 
    注意: これは数学的証明の代替にはならない。
    有限の範囲でしか検証できないためである。
    """
    for n in range(n0, upper + 1):
        if f(n) > c * g(n):
            print(f"  反例発見: n={n}, f(n)={f(n)}, c*g(n)={c * g(n)}")
            return False
    return True
 
 
def find_minimum_c(n0: int, precision: float = 0.01) -> float:
    """
    与えられた n₀ に対して、f(n) ≤ c * g(n) を満たす最小の c を探す。
 
    なぜ最小の c を探すのか:
    - Big-O の定義では「ある c が存在する」ことだけが必要だが、
      最小の c を知ると関数の実際の成長率に対する直感が深まる。
    """
    c = precision
    while c <= 1000:
        if verify_big_o(c, n0, upper=10000):
            return c
        c += precision
    return float('inf')
 
 
if __name__ == "__main__":
    print("=" * 60)
    print("Big-O 記法の定義検証: f(n) = 3n² + 5n + 2 = O(n²)")
    print("=" * 60)
 
    # c=10, n₀=1 での検証
    print("\n【検証1】c=10, n₀=1:")
    result = verify_big_o(c=10, n0=1)
    print(f"  結果: {'成立' if result else '不成立'}")
 
    # c=4, n₀=1 での検証
    print("\n【検証2】c=4, n₀=1:")
    result = verify_big_o(c=4, n0=1)
    print(f"  結果: {'成立' if result else '不成立'}")
 
    # c=3.5, n₀=1 での検証（ギリギリのケース）
    print("\n【検証3】c=3.5, n₀=1:")
    result = verify_big_o(c=3.5, n0=1)
    print(f"  結果: {'成立' if result else '不成立'}")
 
    # c=3.5, n₀=10 での検証
    print("\n【検証4】c=3.5, n₀=10:")
    result = verify_big_o(c=3.5, n0=10)
    print(f"  結果: {'成立' if result else '不成立'}")
 
    # 最小の c を探索
    print("\n【探索】n₀=1 に対する最小の c:")
    min_c = find_minimum_c(n0=1, precision=0.01)
    print(f"  最小 c ≈ {min_c}")
 
    # 比率 f(n)/g(n) の収束を観察
    print("\n【収束確認】f(n)/g(n) の推移:")
    print(f"  {'n':>8} | {'f(n)':>15} | {'g(n)':>15} | {'f(n)/g(n)':>10}")
    print(f"  {'-'*8}-+-{'-'*15}-+-{'-'*15}-+-{'-'*10}")
    for n in [1, 5, 10, 50, 100, 500, 1000, 10000]:
        fn = f(n)
        gn = g(n)
        ratio = fn / gn if gn > 0 else float('inf')
        print(f"  {n:>8} | {fn:>15,} | {gn:>15,} | {ratio:>10.4f}")
 
    print("\n→ n が大きくなると f(n)/g(n) は 3.0 に収束する。")
    print("  これは f(n) の主要項が 3n² であることと一致する。")

#!/usr/bin/env python3
"""
マージソートの計算量 O(n log n) を帰納法の結果と照合して検証する。
実際のマージソートの操作回数をカウントし、理論値と比較する。
"""
 
import math
 
 
class MergeSortCounter:
    """
    マージソートの比較回数を正確にカウントするクラス。
 
    なぜクラスを使うのか:
    - 再帰関数内でカウンタを更新するため、ミュータブルな状態が必要
    - グローバル変数を避け、カプセル化するため
    """
 
    def __init__(self):
        self.comparisons = 0  # 比較回数
        self.assignments = 0  # 代入回数
 
    def reset(self):
        """カウンタをリセットする"""
        self.comparisons = 0
        self.assignments = 0
 
    def merge_sort(self, arr: list) -> list:
        """
        マージソートを実行し、比較・代入回数をカウントする。
 
        返り値: ソート済み配列
        """
        if len(arr) <= 1:
            return arr
 
        mid = len(arr) // 2
        left = self.merge_sort(arr[:mid])
        right = self.merge_sort(arr[mid:])
        return self._merge(left, right)
 
    def _merge(self, left: list, right: list) -> list:
        """2つのソート済み配列をマージする"""
        result = []
        i = j = 0
 
        while i < len(left) and j < len(right):
            self.comparisons += 1
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
            self.assignments += 1
 
        while i < len(left):
            result.append(left[i])
            i += 1
            self.assignments += 1
 
        while j < len(right):
            result.append(right[j])
            j += 1
            self.assignments += 1
 
        return result
 
 
def theoretical_upper_bound(n: int) -> float:
    """
    理論上の上界 c * n * log₂(n) を計算する。
 
    なぜ log₂ を使うのか:
    マージソートは毎回半分に分割するため、再帰の深さは log₂(n)。
    各レベルで O(n) の作業を行うため、合計は n * log₂(n) となる。
    """
    if n <= 1:
        return 0
    return n * math.log2(n)
 
 
if __name__ == "__main__":
    import random
 
    counter = MergeSortCounter()
 
    print("=" * 70)
    print("マージソートの計算量検証: 比較回数 vs 理論値 n·log₂(n)")
    print("=" * 70)
    print(f"{'n':>8} | {'比較回数':>10} | {'n·log₂n':>12} | {'比率':>8} | {'判定':>6}")
    print(f"{'-'*8}-+-{'-'*10}-+-{'-'*12}-+-{'-'*8}-+-{'-'*6}")
 
    for exp in range(1, 16):
        n = 2 ** exp
        arr = list(range(n))
        random.seed(42)  # 再現性のため固定シード
        random.shuffle(arr)
 
        counter.reset()
        sorted_arr = counter.merge_sort(arr[:])
 
        # ソート結果の正当性確認
        assert sorted_arr == sorted(arr), "ソート結果が不正"
 
        theory = theoretical_upper_bound(n)
        ratio = counter.comparisons / theory if theory > 0 else 0
        within = "OK" if ratio <= 1.5 else "WARN"
 
        print(f"{n:>8,} | {counter.comparisons:>10,} | {theory:>12,.1f} | {ratio:>8.4f} | {within:>6}")
 
    print()
    print("→ 比率が定数に収束することから、比較回数 = Θ(n log n) が確認できる。")
    print("  比率が 1.0 以下にならないのは、マージ処理の定数項があるため。")

#!/usr/bin/env python3
"""
二分探索の計算量 O(log n) を帰納法で証明し、数値的に検証する。
 
漸化式: T(n) = T(n/2) + c  (n > 1)
        T(1) = c
 
主張: T(n) ≤ c · (log₂ n + 1) = O(log n)
"""
 
import math
import random
import time
 
 
def binary_search_recursive(arr: list, target: int,
                            lo: int, hi: int,
                            depth: int = 0) -> tuple:
    """
    再帰的二分探索。探索結果と再帰の深さを返す。
 
    なぜ深さを返すのか:
    - 計算量 O(log n) の理論値と実際の再帰深度を比較するため
    - 帰納法の証明結果を数値的に確認できる
 
    返り値: (見つかったインデックス or -1, 再帰深度)
    """
    if lo > hi:
        return (-1, depth)
 
    mid = (lo + hi) // 2
 
    if arr[mid] == target:
        return (mid, depth + 1)
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, hi, depth + 1)
    else:
        return binary_search_recursive(arr, target, lo, mid - 1, depth + 1)
 
 
if __name__ == "__main__":
    print("=" * 60)
    print("二分探索の計算量検証: 再帰深度 vs log₂(n)")
    print("=" * 60)
    print(f"{'n':>10} | {'最大深度':>8} | {'log₂(n)+1':>10} | {'判定':>6}")
    print(f"{'-'*10}-+-{'-'*8}-+-{'-'*10}-+-{'-'*6}")
 
    for exp in range(1, 21):
        n = 2 ** exp
        arr = list(range(n))
 
        # 全要素を探索して最大深度を記録
        max_depth = 0
        for target in [0, n // 4, n // 2, 3 * n // 4, n - 1, n]:
            _, depth = binary_search_recursive(arr, target, 0, n - 1)
            max_depth = max(max_depth, depth)
 
        theory = math.log2(n) + 1
        ok = "OK" if max_depth <= theory + 1 else "WARN"
 
        print(f"{n:>10,} | {max_depth:>8} | {theory:>10.1f} | {ok:>6}")
 
    print()
    print("→ 最大深度は常に log₂(n) + 1 以下に収まっている。")
    print("  これは T(n) = O(log n) と一致する。")

#!/usr/bin/env python3
"""
O(1) 操作の例と、O(1) に見えて実は O(1) でない操作の比較。
 
なぜこの区別が重要なのか:
- 見た目が1行でも計算量が O(1) とは限らない
- 内部で何が行われているかを理解する必要がある
"""
 
 
def constant_time_access(arr: list, index: int) -> int:
    """
    配列の添字アクセス — O(1)
 
    なぜ O(1) なのか:
    配列はメモリ上の連続領域に格納されるため、
    先頭アドレス + index × 要素サイズ で直接アドレスを計算できる。
    この計算は入力サイズに依存しない。
    """
    return arr[index]
 
 
def hash_table_lookup(d: dict, key: str) -> object:
    """
    ハッシュテーブルの参照 — 平均 O(1), 最悪 O(n)
 
    なぜ平均 O(1) なのか:
    ハッシュ関数がキーを均等に分散させるため、
    衝突が少なければ1回のハッシュ計算とメモリアクセスで済む。
 
    なぜ最悪 O(n) なのか:
    全てのキーが同じハッシュ値に衝突した場合、
    連結リストの線形探索が必要になる。
    """
    return d.get(key)
 
 
def looks_constant_but_not(s: str) -> str:
    """
    O(1) に見えるが実は O(n) — 文字列の結合
 
    なぜ O(n) なのか:
    Python の文字列はイミュータブルなので、
    s + "x" は長さ len(s)+1 の新しい文字列を生成する。
    この生成に O(len(s)) のコピーが必要。
    """
    return s + "x"
 
 
if __name__ == "__main__":
    import time
 
    print("=" * 60)
    print("O(1) 操作 vs 隠れた O(n) 操作の比較")
    print("=" * 60)
 
    # 配列アクセスは O(1): サイズに関わらず一定時間
    print("\n【配列の添字アクセス（O(1)）】")
    for size in [100, 10_000, 1_000_000, 100_000_000]:
        arr = list(range(size))
        start = time.perf_counter_ns()
        for _ in range(10000):
            _ = arr[size // 2]
        elapsed = (time.perf_counter_ns() - start) / 10000
        print(f"  サイズ {size:>12,}: 1回あたり {elapsed:>8.1f} ns")
 
    # 文字列結合は O(n): サイズに比例して遅くなる
    print("\n【文字列結合（O(n)に見えないが O(n)）】")
    for size in [100, 1_000, 10_000, 100_000]:
        s = "a" * size
        start = time.perf_counter_ns()
        for _ in range(100):
            _ = s + "x"
        elapsed = (time.perf_counter_ns() - start) / 100
        print(f"  長さ {size:>12,}: 1回あたり {elapsed:>10.1f} ns")

#!/usr/bin/env python3
"""
再帰呼び出しのスタック深度を計測・可視化するプログラム。
様々な再帰アルゴリズムのスタック消費を比較する。
"""
 
import sys
 
 
class StackDepthTracker:
    """
    再帰呼び出しのスタック深度を追跡するクラス。
 
    なぜ追跡が必要か:
    - Python のデフォルトの再帰制限は 1000
    - 再帰深度を意識せずに書くと RecursionError が発生する
    - 空間計算量の分析に再帰深度の情報が不可欠
    """
 
    def __init__(self):
        self.max_depth = 0
        self.current_depth = 0
 
    def enter(self):
        """再帰呼び出し開始時に呼ぶ"""
        self.current_depth += 1
        self.max_depth = max(self.max_depth, self.current_depth)
 
    def leave(self):
        """再帰呼び出し終了時に呼ぶ"""
        self.current_depth -= 1
 
    def reset(self):
        """カウンタをリセット"""
        self.max_depth = 0
        self.current_depth = 0
 
 
def fib_naive(n: int, tracker: StackDepthTracker) -> int:
    """
    フィボナッチ数の素朴再帰。
    時間: O(2ⁿ), 空間: O(n)（スタック深度）
    """
    tracker.enter()
    try:
        if n <= 1:
            return n
        result = fib_naive(n - 1, tracker) + fib_naive(n - 2, tracker)
        return result
    finally:
        tracker.leave()
 
 
def factorial_recursive(n: int, tracker: StackDepthTracker) -> int:
    """
    階乗の再帰計算。
    時間: O(n), 空間: O(n)（スタック深度）
    """
    tracker.enter()
    try:
        if n <= 1:
            return 1
        return n * factorial_recursive(n - 1, tracker)
    finally:
        tracker.leave()
 
 
def binary_search_rec(arr: list, target: int,
                      lo: int, hi: int,
                      tracker: StackDepthTracker) -> int:
    """
    二分探索の再帰版。
    時間: O(log n), 空間: O(log n)（スタック深度）
    """
    tracker.enter()
    try:
        if lo > hi:
            return -1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search_rec(arr, target, mid + 1, hi, tracker)
        else:
            return binary_search_rec(arr, target, lo, mid - 1, tracker)
    finally:
        tracker.leave()
 
 
if __name__ == "__main__":
    tracker = StackDepthTracker()
 
    print("=" * 60)
    print("再帰アルゴリズムのスタック深度比較")
    print("=" * 60)
 
    # フィボナッチ（素朴再帰）— 空間 O(n)
    print("\n【フィボナッチ（素朴再帰）】空間 O(n)")
    for n in [5, 10, 15, 20]:
        tracker.reset()
        fib_naive(n, tracker)
        print(f"  fib({n:>2}): 最大スタック深度 = {tracker.max_depth}")
 
    # 階乗（再帰）— 空間 O(n)
    print("\n【階乗（再帰）】空間 O(n)")
    for n in [5, 10, 50, 100]:
        tracker.reset()
        factorial_recursive(n, tracker)
        print(f"  {n:>3}!: 最大スタック深度 = {tracker.max_depth}")
 
    # 二分探索（再帰）— 空間 O(log n)
    print("\n【二分探索（再帰）】空間 O(log n)")
    for exp in [4, 8, 12, 16, 20]:
        n = 2 ** exp
        arr = list(range(n))
        tracker.reset()
        binary_search_rec(arr, n - 1, 0, n - 1, tracker)
        print(f"  n={n:>8,}: 最大スタック深度 = {tracker.max_depth:>3}"
              f"  (log₂ n = {exp})")
 
    print()
    print("→ 二分探索の再帰版は空間 O(log n)。")
    print("  反復版（while ループ）に書き換えると空間 O(1) になる。")
    print("  空間効率が重要な場合は反復版を選ぶべきである。")

#!/usr/bin/env python3
"""
フィボナッチ数の計算: 時間と空間のトレードオフを実証する。
 
3つの実装を比較し、トレードオフを数値的に確認する。
"""
 
import time
from functools import lru_cache
 
 
def fib_naive(n: int) -> int:
    """
    素朴再帰: 時間 O(2ⁿ), 空間 O(n)
 
    なぜ遅いのか:
    同じ部分問題を何度も計算する。fib(30) を求めるのに
    fib(1) は 832,040 回も呼ばれる。
    """
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
 
def fib_memoized(n: int, memo: dict = None) -> int:
    """
    メモ化再帰: 時間 O(n), 空間 O(n)
 
    なぜ速いのか:
    各部分問題を一度だけ計算し、結果を辞書に保存する。
    2回目以降は辞書参照（O(1)）で済む。
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]
 
 
def fib_iterative(n: int) -> int:
    """
    反復（ボトムアップ）: 時間 O(n), 空間 O(1)
 
    なぜ空間 O(1) なのか:
    直前の2つの値だけを保持すれば十分。
    配列全体を保存する必要がない。
    """
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1
 
 
if __name__ == "__main__":
    print("=" * 65)
    print("フィボナッチ数の計算: 時間と空間のトレードオフ")
    print("=" * 65)
 
    # 正当性確認
    for n in range(20):
        assert fib_iterative(n) == fib_memoized(n)
 
    # 性能比較（小さい n で素朴版も含む）
    print(f"\n{'方法':>14} | {'n':>6} | {'結果':>15} | {'所要時間':>12}")
    print(f"{'-'*14}-+-{'-'*6}-+-{'-'*15}-+-{'-'*12}")
 
    for n in [10, 20, 30, 35]:
        # 素朴再帰
        start = time.perf_counter()
        result = fib_naive(n)
        elapsed_naive = time.perf_counter() - start
 
        # メモ化再帰
        start = time.perf_counter()
        result_memo = fib_memoized(n)
        elapsed_memo = time.perf_counter() - start
 
        # 反復
        start = time.perf_counter()
        result_iter = fib_iterative(n)
        elapsed_iter = time.perf_counter() - start
 
        print(f"{'素朴再帰':>14} | {n:>6} | {result:>15,} | {elapsed_naive:>10.6f} s")
        print(f"{'メモ化':>14} | {n:>6} | {result_memo:>15,} | {elapsed_memo:>10.6f} s")
        print(f"{'反復':>14} | {n:>6} | {result_iter:>15,} | {elapsed_iter:>10.6f} s")
        print(f"{'-'*14}-+-{'-'*6}-+-{'-'*15}-+-{'-'*12}")
 
    # 大きい n（素朴版は遅すぎるので除外）
    print(f"\n大きい n での比較（素朴再帰は省略）:")
    print(f"{'方法':>14} | {'n':>6} | {'所要時間':>12}")
    print(f"{'-'*14}-+-{'-'*6}-+-{'-'*12}")
 
    for n in [100, 500, 1000, 5000]:
        start = time.perf_counter()
        fib_memoized(n, {})
        elapsed_memo = time.perf_counter() - start
 
        start = time.perf_counter()
        fib_iterative(n)
        elapsed_iter = time.perf_counter() - start
 
        print(f"{'メモ化':>14} | {n:>6} | {elapsed_memo:>10.6f} s")
        print(f"{'反復':>14} | {n:>6} | {elapsed_iter:>10.6f} s")
        print(f"{'-'*14}-+-{'-'*6}-+-{'-'*12}")
 
    print()
    print("→ メモ化と反復は同じ時間計算量 O(n) だが、")
    print("  反復版は空間 O(1) で済むため、大きい n では有利。")

#!/usr/bin/env python3
"""
Python の list の内部容量変化を観察し、償却 O(1) を検証する。
 
sys.getsizeof() を使って list オブジェクトのメモリサイズを追跡する。
"""
 
import sys
 
 
def observe_list_growth(max_elements: int = 100) -> list:
    """
    list に要素を1つずつ追加し、メモリサイズの変化を記録する。
 
    なぜ sys.getsizeof を使うのか:
    - list オブジェクト自体のサイズ（ポインタ配列の容量）を取得できる
    - 要素の中身のサイズは含まないが、容量変化の観察には十分
    """
    records = []
    lst = []
    prev_size = sys.getsizeof(lst)
 
    for i in range(max_elements):
        lst.append(i)
        curr_size = sys.getsizeof(lst)
        if curr_size != prev_size:
            records.append({
                'index': i,
                'elements': i + 1,
                'size_bytes': curr_size,
                'growth': curr_size - prev_size,
                'resized': True
            })
        else:
            records.append({
                'index': i,
                'elements': i + 1,
                'size_bytes': curr_size,
                'growth': 0,
                'resized': False
            })
        prev_size = curr_size
 
    return records
 
 
def calculate_amortized_cost(records: list) -> None:
    """
    集約法による償却コストを計算する。
 
    各リサイズを「高コスト操作」としてカウントし、
    全操作の平均コストを求める。
    """
    total_cost = 0
    resize_count = 0
 
    for r in records:
        if r['resized']:
            # リサイズ時のコスト = 既存要素のコピー + 追加
            total_cost += r['elements']
            resize_count += 1
        else:
            # 通常の追加
            total_cost += 1
 
    n = len(records)
    amortized = total_cost / n if n > 0 else 0
 
    print(f"\n  全 {n} 回の操作:")
    print(f"    合計コスト: {total_cost}")
    print(f"    リサイズ回数: {resize_count}")
    print(f"    償却コスト: {amortized:.2f} = O(1)")
 
 
if __name__ == "__main__":
    print("=" * 65)
    print("Python list の動的配列としての振る舞い")
    print("=" * 65)
 
    records = observe_list_growth(100)
 
    print("\nリサイズが発生したタイミング:")
    print(f"  {'要素数':>6} | {'サイズ(bytes)':>12} | {'増加量(bytes)':>13}")
    print(f"  {'-'*6}-+-{'-'*12}-+-{'-'*13}")
 
    for r in records:
        if r['resized']:
            print(f"  {r['elements']:>6} | {r['size_bytes']:>12} | +{r['growth']:>12}")
 
    calculate_amortized_cost(records)
 
    # 大規模での検証
    print("\n" + "=" * 65)
    print("大規模データでの償却コスト検証")
    print("=" * 65)
 
    for n in [1_000, 10_000, 100_000, 1_000_000]:
        lst = []
        resize_count = 0
        prev_size = sys.getsizeof(lst)
 
        for i in range(n):
            lst.append(i)
            curr_size = sys.getsizeof(lst)
            if curr_size != prev_size:
                resize_count += 1
                prev_size = curr_size
 
        print(f"  n={n:>10,}: リサイズ回数 = {resize_count:>4}"
              f"  (log₂ n ≈ {n.bit_length():>3})")
 
    print()
    print("→ リサイズ回数は O(log n) であり、全操作の合計は O(n)。")
    print("  したがって1回あたりの償却コストは O(1)。")

#!/usr/bin/env python3
"""
コードの見た目と実際の計算量が異なる典型的なケースを示す。
 
なぜこれが重要か:
- コードレビューで計算量の問題を見抜くには、
  各操作の内部コストを理解する必要がある
- 「1行 = O(1)」という思い込みは危険
"""
 
 
def hidden_quadratic_string(n: int) -> str:
    """
    【落とし穴1】文字列の繰り返し結合 — 見た目 O(n)、実質 O(n²)
 
    なぜ O(n²) なのか:
    Python の文字列はイミュータブル。各 += で新しい文字列が生成される。
    i 回目の結合で長さ i の文字列をコピーするため、
    合計 = 1 + 2 + ... + n = n(n+1)/2 = O(n²)
 
    正しい方法: リストに追加して最後に join する → O(n)
    """
    result = ""
    for i in range(n):
        result += "a"  # 毎回 O(i) のコピー
    return result
 
 
def correct_string_building(n: int) -> str:
    """O(n) での文字列構築"""
    parts = []
    for i in range(n):
        parts.append("a")  # O(1) 償却
    return "".join(parts)  # O(n) で結合
 
 
def hidden_quadratic_list(arr: list) -> list:
    """
    【落とし穴2】リスト先頭への挿入 — 見た目 O(n)、実質 O(n²)
 
    なぜ O(n²) なのか:
    list.insert(0, x) はリスト全体を1つずつ後ろにシフトする必要がある。
    i 回目の挿入で i 個の要素をシフトするため、合計 O(n²)。
 
    正しい方法: collections.deque を使う → appendleft が O(1)
    """
    result = []
    for x in arr:
        result.insert(0, x)  # 毎回 O(len(result)) のシフト
    return result
 
 
def hidden_quadratic_membership(arr: list, targets: list) -> list:
    """
    【落とし穴3】リストでの in 演算 — 見た目 O(n)、実質 O(n²)
 
    なぜ O(n²) なのか:
    list の `in` 演算は O(n) の線形探索。
    n 個のターゲットそれぞれに対して O(n) なので合計 O(n²)。
 
    正しい方法: set に変換してから判定 → O(n) で済む
    """
    found = []
    for target in targets:
        if target in arr:  # O(n) の線形探索
            found.append(target)
    return found
 
 
def correct_membership(arr: list, targets: list) -> list:
    """set を使った O(n) の所属判定"""
    arr_set = set(arr)  # O(n) で set を構築
    found = []
    for target in targets:
        if target in arr_set:  # O(1) のハッシュ参照
            found.append(target)
    return found
 
 
if __name__ == "__main__":
    import time
 
    print("=" * 65)
    print("隠れた O(n²) パターンの検出と修正")
    print("=" * 65)
 
    # パターン1: 文字列結合
    print("\n【パターン1: 文字列結合】")
    for n in [1000, 5000, 10000, 50000]:
        start = time.perf_counter()
        hidden_quadratic_string(n)
        t_bad = time.perf_counter() - start
 
        start = time.perf_counter()
        correct_string_building(n)
        t_good = time.perf_counter() - start
 
        speedup = t_bad / t_good if t_good > 0 else float('inf')
        print(f"  n={n:>6}: += {t_bad:.4f}s | join {t_good:.6f}s"
              f" | 高速化: {speedup:.0f}x")
 
    # パターン3: 所属判定
    print("\n【パターン3: 所属判定】")
    for n in [1000, 5000, 10000, 50000]:
        arr = list(range(n))
        targets = list(range(0, n, 2))  # 偶数のみ
 
        start = time.perf_counter()
        hidden_quadratic_membership(arr, targets)
        t_bad = time.perf_counter() - start
 
        start = time.perf_counter()
        correct_membership(arr, targets)
        t_good = time.perf_counter() - start
 
        speedup = t_bad / t_good if t_good > 0 else float('inf')
        print(f"  n={n:>6}: list {t_bad:.4f}s | set {t_good:.6f}s"
              f" | 高速化: {speedup:.0f}x")
 
    print()
    print("→ n が大きくなるほど高速化の倍率が増加する。")
    print("  これは O(n²) vs O(n) の差が顕在化しているため。")

# BAD: "ループが2回あるから O(2n) だ" → 誤り
def double_pass(arr: list) -> int:
    """
    2回の線形走査を行う関数。
 
    誤った分析: O(2n)
    正しい分析: O(n)
 
    なぜ定数係数を無視するのか:
    漸近記法は入力サイズが大きくなったときの「成長率」を表現する。
    2n も 100n も n に対して線形に成長するため、同じ O(n) である。
    定数係数はハードウェアや言語実装に依存する部分であり、
    アルゴリズムの本質的な効率とは別の問題である。
    """
    total = 0
    for x in arr:     # 第1パス: O(n)
        total += x
    for x in arr:     # 第2パス: O(n)
        total += x * 2
    return total
    # O(n) + O(n) = O(n) ← 定数倍は吸収される
 
 
# 同様の誤り:
# × O(n/2) → ○ O(n)   （半分のループでも線形は線形）
# × O(3n²) → ○ O(n²)  （定数倍は無視）
# × O(n² + n) → ○ O(n²) （低次項も無視）

# BAD: "クイックソートは O(n log n)" → 不完全
def quicksort(arr: list) -> list:
    """
    クイックソートの計算量を正確に述べると:
 
    - 最良ケース: O(n log n)  ← ピボットが毎回中央値
    - 平均ケース: O(n log n)  ← ランダムな入力
    - 最悪ケース: O(n²)       ← ソート済みの入力 + 先頭ピボット
 
    なぜケースの区別が重要か:
    「O(n log n)」とだけ述べると、最悪ケースの O(n²) が隠蔽される。
    セキュリティの文脈では、攻撃者が意図的に最悪ケースを引き起こす
    ことが可能な場合がある（例: ハッシュテーブルの衝突攻撃）。
 
    正しい記述例:
    「クイックソートの平均計算量は O(n log n)、最悪計算量は O(n²)。
     ランダム化ピボット選択により最悪ケースの確率を無視できるほど
     小さくできる。」
    """
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 先頭をピボットに（最悪ケースの原因）
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)
 
 
# GOOD: ランダム化ピボットで最悪ケースを回避
import random
 
def quicksort_randomized(arr: list) -> list:
    """
    ランダム化クイックソート。
    平均・期待計算量: O(n log n)
    最悪計算量: O(n²)（ただし確率は非常に低い）
    """
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # ランダムにピボットを選択
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort_randomized(left) + middle + quicksort_randomized(right)

# BAD: 時間計算量だけ考えて空間計算量を無視する
def get_all_pairs(arr: list) -> list:
    """
    全ペアを生成する。
    時間: O(n²)
    空間: O(n²) ← これを無視すると危険
 
    なぜ危険か:
    n = 100,000 の場合、ペア数は 10^10。
    各ペアが8バイトとすると約 80GB のメモリが必要。
    これは大半のマシンのメモリを超える。
 
    対策:
    1. ジェネレータを使い、全ペアを同時にメモリに保持しない
    2. 必要なペアだけを生成するアルゴリズムに変更する
    """
    return [(a, b) for a in arr for b in arr]  # O(n²) の空間
 
 
# GOOD: ジェネレータで空間 O(1) に
def get_all_pairs_generator(arr: list):
    """ペアを1つずつ生成 — 時間 O(n²), 空間 O(1)"""
    for a in arr:
        for b in arr:
            yield (a, b)

#!/usr/bin/env python3
"""
エッジケースでの計算量の振る舞いを検証する。
 
なぜエッジケースが重要か:
- 漸近記法は「十分大きな n」に対する記述だが、
  実際のプログラムでは n=0 や n=1 も処理する必要がある
- エッジケースでの定数時間の処理を忘れると、
  ゼロ除算やインデックスエラーの原因になる
"""
 
 
def binary_search(arr: list, target: int) -> int:
    """
    二分探索: O(log n) だが、n=0 や n=1 の場合はどうなるか？
 
    n = 0: ループに入らず即座に -1 を返す → O(1)
    n = 1: 1回の比較で完了 → O(1)
 
    漸近記法的には O(log n) に含まれる（O(1) ⊂ O(log n)）が、
    実装上はこれらのケースを明示的に処理するのが安全。
    """
    if not arr:  # n = 0 の処理
        return -1
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
 
def merge_sort(arr: list) -> list:
    """
    マージソート: O(n log n) だが、n ≤ 1 では再帰しない。
 
    多くの実装では n が小さい場合に挿入ソートに切り替える。
    なぜなら、小さい n では挿入ソートの方が定数項が小さく高速だから。
    一般的な閾値は n = 16〜64 程度。
    """
    if len(arr) <= 1:
        return arr[:]
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
 
    # マージ処理
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
if __name__ == "__main__":
    # エッジケースのテスト
    print("=" * 50)
    print("エッジケースでの動作検証")
    print("=" * 50)
 
    # n = 0
    assert binary_search([], 5) == -1
    assert merge_sort([]) == []
    print("n=0: 全テスト合格")
 
    # n = 1
    assert binary_search([5], 5) == 0
    assert binary_search([5], 3) == -1
    assert merge_sort([42]) == [42]
    print("n=1: 全テスト合格")
 
    # n = 2
    assert binary_search([1, 3], 3) == 1
    assert merge_sort([3, 1]) == [1, 3]
    print("n=2: 全テスト合格")
 
    print("\n→ エッジケースでも正しく動作することを確認。")

def func_a(n: int) -> int:
    total = 0
    for i in range(n):
        for j in range(10):
            total += i * j
    return total
 
 
def func_b(n: int) -> int:
    total = 0
    i = 1
    while i < n:
        total += i
        i *= 2
    return total
 
 
def func_c(arr: list) -> list:
    result = []
    for x in arr:
        if x not in result:
            result.append(x)
    return result

def mystery(n: int) -> int:
    if n <= 0:
        return 0
    return mystery(n - 1) + mystery(n - 1)

class MultiStack:
    def __init__(self):
        self.stack = []
 
    def push(self, x):
        """要素を1つ追加 — コスト 1"""
        self.stack.append(x)
 
    def multipop(self, k):
        """最大 k 個の要素をポップ — コスト min(k, len(stack))"""
        count = min(k, len(self.stack))
        for _ in range(count):
            self.stack.pop()
        return count

def process(data: list) -> list:
    result = []
    for item in data:                  # n 回
        result = result + [item]       # ← この行に注目
    return result

def count_triples(arr: list, target: int) -> int:
    """arr の中から合計が target になる3つ組の個数を数える"""
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if arr[i] + arr[j] + arr[k] == target:
                    count += 1
    return count

# 例1: 文字列の繰り返し連結
s = ""
for i in range(n):
    s += str(i)  # 毎回新しい文字列を生成 → O(1+2+...+n) = O(n²)
 
# 例2: リスト先頭への挿入
result = []
for x in data:
    result.insert(0, x)  # 毎回全要素をシフト → O(n²)
 
# 例3: 再帰展開
# T(n) = T(n-1) + n → T(n) = n + (n-1) + ... + 1 = O(n²)