"""
漸近記法の増加率を数値的に比較するプログラム。
なぜこの比較が重要か: アルゴリズム選択時に、入力サイズの増加が
実行時間にどう影響するかを直感的に理解するためである。
"""
 
import math
 
 
def compare_growth_rates(sizes: list[int]) -> None:
    """異なる計算量クラスの増加率を表形式で表示する。
 
    Args:
        sizes: 比較する入力サイズのリスト
    """
    header = f"{'n':>10} | {'log n':>10} | {'n':>10} | {'n log n':>12} | {'n^2':>12} | {'2^n':>15}"
    separator = "-" * len(header)
 
    print(header)
    print(separator)
 
    for n in sizes:
        log_n = math.log2(n) if n > 0 else 0
        n_log_n = n * log_n
        n_squared = n * n
        # 2^n は n が大きいと天文学的数値になるため、上限を設ける
        two_to_n = 2 ** n if n <= 30 else float("inf")
 
        print(
            f"{n:>10} | "
            f"{log_n:>10.2f} | "
            f"{n:>10} | "
            f"{n_log_n:>12.1f} | "
            f"{n_squared:>12} | "
            f"{two_to_n:>15}"
        )
 
 
def main() -> None:
    sizes = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
    compare_growth_rates(sizes)
    print()
 
    # 計算量クラス間の「壁」を実感する
    print("=== n=20 における各関数の値 ===")
    n = 20
    print(f"  log n    = {math.log2(n):.2f}")
    print(f"  n        = {n}")
    print(f"  n log n  = {n * math.log2(n):.1f}")
    print(f"  n^2      = {n**2}")
    print(f"  n^3      = {n**3}")
    print(f"  2^n      = {2**n}")
    print(f"  n!       = {math.factorial(n)}")
    # 2^20 = 1,048,576 に対し 20! = 2,432,902,008,176,640,000
    # この差が「指数時間 vs 階乗時間」の壁を示している
 
 
if __name__ == "__main__":
    main()

"""
線形探索における最悪・平均・最良ケースの解析。
同じアルゴリズムでも、ターゲットの位置により比較回数が大きく異なることを示す。
"""
 
import random
import statistics
 
 
def linear_search(arr: list[int], target: int) -> tuple[int, int]:
    """線形探索を行い、見つかったインデックスと比較回数を返す。
 
    Args:
        arr: 探索対象の配列
        target: 探索する値
 
    Returns:
        (見つかったインデックス, 比較回数) のタプル。
        見つからない場合はインデックスに -1 を返す。
    """
    comparisons = 0
    for i, val in enumerate(arr):
        comparisons += 1
        if val == target:
            return i, comparisons
    return -1, comparisons
 
 
def analyze_linear_search(n: int, trials: int = 10000) -> None:
    """線形探索の最悪・平均・最良ケースを実験的に分析する。
 
    なぜ実験的分析を行うか: 理論値との一致を確認することで、
    漸近解析の妥当性を検証するためである。
 
    Args:
        n: 配列のサイズ
        trials: 試行回数
    """
    arr = list(range(n))
 
    # 最良ケース: ターゲットが先頭にある場合
    _, best_comparisons = linear_search(arr, 0)
 
    # 最悪ケース: ターゲットが存在しない場合
    _, worst_comparisons = linear_search(arr, n + 1)
 
    # 平均ケース: ターゲットの位置がランダム
    comparison_counts = []
    for _ in range(trials):
        target = random.randint(0, n - 1)
        _, comps = linear_search(arr, target)
        comparison_counts.append(comps)
 
    avg_comparisons = statistics.mean(comparison_counts)
 
    print(f"=== 線形探索の解析 (n={n}) ===")
    print(f"  最良ケース: {best_comparisons} 回の比較   (理論値: 1)")
    print(f"  最悪ケース: {worst_comparisons} 回の比較   (理論値: {n})")
    print(f"  平均ケース: {avg_comparisons:.1f} 回の比較 (理論値: {(n + 1) / 2:.1f})")
    print()
 
    # 理論値との誤差を確認
    theoretical_avg = (n + 1) / 2
    error_pct = abs(avg_comparisons - theoretical_avg) / theoretical_avg * 100
    print(f"  平均ケースの理論値との誤差: {error_pct:.2f}%")
    # 試行回数が十分なら、この誤差は 1% 以下に収まることが想定される
 
 
def main() -> None:
    for n in [100, 1000, 10000]:
        analyze_linear_search(n)
        print()
 
 
if __name__ == "__main__":
    main()

"""
クイックソートにおける最悪・平均・最良ケースの具体例。
ピボット選択がアルゴリズムの性能にどのように影響するかを示す。
"""
 
import random
import time
 
 
def quicksort_count(arr: list[int]) -> tuple[list[int], int]:
    """クイックソート（先頭ピボット）を行い、比較回数も返す。
 
    なぜ先頭ピボットを使うか: 最悪ケースが発生しやすい実装として、
    ピボット選択の重要性を示すためである。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        (ソート済みリスト, 比較回数) のタプル
    """
    if len(arr) <= 1:
        return arr[:], 0
 
    pivot = arr[0]  # 先頭要素をピボットにする（意図的に単純な選択）
    left = []
    right = []
    comparisons = 0
 
    for x in arr[1:]:
        comparisons += 1
        if x <= pivot:
            left.append(x)
        else:
            right.append(x)
 
    sorted_left, left_comps = quicksort_count(left)
    sorted_right, right_comps = quicksort_count(right)
 
    return sorted_left + [pivot] + sorted_right, comparisons + left_comps + right_comps
 
 
def demonstrate_quicksort_cases(n: int) -> None:
    """クイックソートの三つのケースを実験的に示す。
 
    Args:
        n: 配列のサイズ
    """
    print(f"=== クイックソートの解析 (n={n}) ===")
 
    # 最悪ケース: 既にソート済みの配列（先頭ピボットでは最悪）
    sorted_arr = list(range(n))
    _, worst_comps = quicksort_count(sorted_arr)
    print(f"  最悪ケース（ソート済み）: {worst_comps} 回の比較")
    print(f"    → 想定される計算量: O(n^2) = {n * (n - 1) // 2}")
 
    # 最良ケース: 毎回中央値がピボットになるケース
    # （実際に毎回中央値になる配列を構築するのは複雑なので、理論値を示す）
    import math
    theoretical_best = n * math.log2(max(n, 1))
    print(f"  最良ケースの理論値: O(n log n) ≈ {theoretical_best:.0f}")
 
    # 平均ケース: ランダムな配列
    total_comps = 0
    trials = 100
    for _ in range(trials):
        random_arr = list(range(n))
        random.shuffle(random_arr)
        _, comps = quicksort_count(random_arr)
        total_comps += comps
    avg_comps = total_comps / trials
    # 平均ケースの理論値: 2n ln n ≈ 1.39 n log_2 n
    theoretical_avg = 1.39 * n * math.log2(max(n, 1))
    print(f"  平均ケース（{trials}回平均）: {avg_comps:.0f} 回の比較")
    print(f"    → 理論値 1.39 n log n ≈ {theoretical_avg:.0f}")
    print()
 
 
def main() -> None:
    # n=500 程度なら最悪ケースでもスタックオーバーフローしない
    for n in [50, 100, 500]:
        demonstrate_quicksort_cases(n)
 
 
if __name__ == "__main__":
    main()

"""
動的配列（倍増戦略）の償却解析。
三つの手法（集約法、配賦法、ポテンシャル法）を実装で示す。
"""
 
 
class DynamicArray:
    """倍増戦略を用いた動的配列の実装。
 
    なぜ倍増戦略を使うか:
    配列が満杯になったとき、容量を 2 倍にする。毎回 1 だけ増やす戦略では
    n 回の append に O(n^2) のコストがかかるが、倍増戦略なら O(n) で済む。
    この差は容量拡張の頻度に由来する。
    """
 
    def __init__(self) -> None:
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity
        self._total_cost = 0  # コスト追跡用
        self._operation_costs: list[int] = []  # 各操作のコスト記録
 
    def append(self, value: int) -> int:
        """要素を末尾に追加し、この操作のコスト（要素コピー回数 + 1）を返す。
 
        Args:
            value: 追加する値
 
        Returns:
            この操作にかかったコスト
        """
        cost = 1  # 要素の書き込みコスト
 
        if self._size == self._capacity:
            # 容量拡張: 全要素をコピーするコストが発生
            cost += self._size  # コピーコスト
            new_data = [None] * (self._capacity * 2)
            for i in range(self._size):
                new_data[i] = self._data[i]
            self._data = new_data
            self._capacity *= 2
 
        self._data[self._size] = value
        self._size += 1
        self._total_cost += cost
        self._operation_costs.append(cost)
        return cost
 
    @property
    def size(self) -> int:
        return self._size
 
    @property
    def capacity(self) -> int:
        return self._capacity
 
    @property
    def total_cost(self) -> int:
        return self._total_cost
 
 
def demonstrate_aggregate_method(n: int) -> None:
    """集約法による償却解析のデモンストレーション。
 
    集約法の考え方:
    n 回の append の合計コストを直接計算する。
    拡張が起きるのは i = 1, 2, 4, 8, ..., 2^k の時点で、
    拡張コストは 1 + 2 + 4 + ... + 2^k <= 2n。
    書き込みコストは n。
    よって合計コスト <= 3n → 一操作あたり O(1)。
    """
    arr = DynamicArray()
    print(f"=== 集約法による解析 (n={n}) ===")
    print(f"{'操作番号':>8} | {'この操作のコスト':>16} | {'累積コスト':>10} | {'容量':>6}")
    print("-" * 50)
 
    for i in range(1, n + 1):
        cost = arr.append(i)
        if cost > 1 or i <= 5 or i == n:  # 拡張時と先頭・末尾を表示
            print(f"{i:>8} | {cost:>16} | {arr.total_cost:>10} | {arr.capacity:>6}")
 
    amortized = arr.total_cost / n
    print(f"\n  合計コスト: {arr.total_cost}")
    print(f"  操作回数: {n}")
    print(f"  一操作あたりの償却コスト: {amortized:.2f}")
    print(f"  → 理論的な上界: 3.0 (3n/n)")
    print()
 
 
def demonstrate_accounting_method(n: int) -> None:
    """配賦法による償却解析のデモンストレーション。
 
    配賦法の考え方:
    各 append 操作に「償却コスト 3」を請求する。
      - 1: 要素の書き込み
      - 2: 将来の拡張に備えた「貯金」
    拡張時には、貯金されたコインで全コピーを賄う。
    """
    print(f"=== 配賦法による解析 (n={n}) ===")
    balance = 0  # 貯金残高
    amortized_cost_per_op = 3  # 各操作に請求する償却コスト
 
    capacity = 1
    size = 0
    all_balanced = True
 
    for i in range(1, n + 1):
        balance += amortized_cost_per_op  # 3 コインを請求
        balance -= 1  # 書き込みに 1 コイン使用
 
        if size == capacity:
            # 拡張: size 個のコピーにコインを使用
            balance -= size
            capacity *= 2
            if balance < 0:
                all_balanced = False
 
        size += 1
 
    print(f"  各操作への請求額: {amortized_cost_per_op}")
    print(f"  最終的な貯金残高: {balance}")
    print(f"  貯金が負にならなかったか: {'はい' if all_balanced else 'いいえ'}")
    print(f"  → 貯金が常に非負なら、償却コスト {amortized_cost_per_op} は正当")
    print()
 
 
def demonstrate_potential_method(n: int) -> None:
    """ポテンシャル法による償却解析のデモンストレーション。
 
    ポテンシャル法の考え方:
    ポテンシャル関数 Phi(D) = 2 * size - capacity と定義する。
    (ここで D はデータ構造の状態)
 
    償却コスト = 実コスト + Phi(D_after) - Phi(D_before)
 
    拡張なしの場合:
      実コスト = 1
      Phi 変化 = 2(size+1) - cap - (2*size - cap) = 2
      償却コスト = 1 + 2 = 3
 
    拡張ありの場合 (size == capacity のとき):
      実コスト = 1 + size (コピー)
      新容量 = 2 * capacity
      Phi_after = 2(size+1) - 2*capacity = 2*size + 2 - 2*size = 2
      Phi_before = 2*size - capacity = 2*size - size = size
      Phi 変化 = 2 - size
      償却コスト = (1 + size) + (2 - size) = 3
    """
    print(f"=== ポテンシャル法による解析 (n={n}) ===")
 
    capacity = 1
    size = 0
 
    for i in range(1, min(n, 20) + 1):
        phi_before = 2 * size - capacity
 
        actual_cost = 1
        expanded = False
        if size == capacity:
            actual_cost += size
            capacity *= 2
            expanded = True
 
        size += 1
        phi_after = 2 * size - capacity
        amortized = actual_cost + phi_after - phi_before
 
        if expanded or i <= 5:
            print(
                f"  操作 {i:>3}: "
                f"実コスト={actual_cost:>4}, "
                f"Phi変化={phi_after - phi_before:>4}, "
                f"償却コスト={amortized:>2}"
                f"{'  ← 拡張' if expanded else ''}"
            )
 
    print(f"  → すべての操作で償却コスト = 3（定数）")
    print()
 
 
def main() -> None:
    n = 64
    demonstrate_aggregate_method(n)
    demonstrate_accounting_method(n)
    demonstrate_potential_method(n)
 
 
if __name__ == "__main__":
    main()

"""
MultiPop 付きスタックの償却解析。
push は O(1)、multi_pop(k) は O(min(k, size)) だが、
n 回の操作列全体の償却コストは一操作あたり O(1) であることを示す。
"""
 
 
class StackWithMultiPop:
    """MultiPop 操作を持つスタック。
 
    なぜ償却解析が必要か:
    multi_pop(k) は最悪 O(n) だが、pop できるのは push された要素だけである。
    n 回の操作列中の pop 合計回数は push 回数を超えないため、
    全操作の合計コストは O(n) に収まる。
    """
 
    def __init__(self) -> None:
        self._stack: list[int] = []
        self._total_cost = 0
 
    def push(self, value: int) -> int:
        """要素をプッシュする。コスト: 1。"""
        self._stack.append(value)
        self._total_cost += 1
        return 1
 
    def multi_pop(self, k: int) -> tuple[list[int], int]:
        """最大 k 個の要素をポップする。コスト: min(k, size)。
 
        Args:
            k: ポップする最大個数
 
        Returns:
            (取り出した要素のリスト, コスト)
        """
        actual_pops = min(k, len(self._stack))
        popped = []
        for _ in range(actual_pops):
            popped.append(self._stack.pop())
        self._total_cost += actual_pops
        return popped, actual_pops
 
    @property
    def size(self) -> int:
        return len(self._stack)
 
    @property
    def total_cost(self) -> int:
        return self._total_cost
 
 
def demonstrate_multipop_amortized() -> None:
    """MultiPop スタックの償却解析デモ。"""
    stack = StackWithMultiPop()
    operations = []
 
    # 操作列: push を多数行い、時折 multi_pop で一気に取り出す
    import random
    random.seed(42)
 
    n = 100
    for i in range(n):
        if random.random() < 0.7 or stack.size == 0:
            cost = stack.push(i)
            operations.append(("push", cost))
        else:
            k = random.randint(1, stack.size)
            _, cost = stack.multi_pop(k)
            operations.append((f"multi_pop({k})", cost))
 
    print(f"=== MultiPop スタックの償却解析 ===")
    print(f"  操作回数: {n}")
    print(f"  合計コスト: {stack.total_cost}")
    print(f"  一操作あたりの償却コスト: {stack.total_cost / n:.2f}")
    print(f"  → 理論的な償却コスト: O(1)")
    print()
 
    # 最悪の個別操作のコストを確認
    max_cost = max(cost for _, cost in operations)
    print(f"  個別操作の最大コスト: {max_cost}")
    print(f"  → 個別の最悪ケースは O(n) だが、償却では O(1)")
 
 
if __name__ == "__main__":
    demonstrate_multipop_amortized()

"""
マージソートの漸化式導出。
各行のコストをコメントで注釈し、漸化式の構成要素を明示する。
"""
 
 
def merge_sort(arr: list[int]) -> list[int]:
    """マージソート — T(n) = 2T(n/2) + O(n)
 
    漸化式の導出:
    - ベースケース: len(arr) <= 1 のとき O(1)
    - 再帰呼び出し: 2 回、各サイズ n/2 → 2T(n/2)
    - 統合コスト: merge は各要素を 1 回ずつ見る → O(n)
    """
    if len(arr) <= 1:                  # O(1) — ベースケース
        return arr
 
    mid = len(arr) // 2                # O(1) — 分割位置の計算
    left = merge_sort(arr[:mid])       # T(n/2) — 左半分を再帰的にソート
    right = merge_sort(arr[mid:])      # T(n/2) — 右半分を再帰的にソート
    return merge(left, right)          # O(n) — 統合
 
 
def merge(left: list[int], right: list[int]) -> list[int]:
    """二つのソート済みリストを統合する。コスト: O(n)。
 
    なぜ O(n) か: 各要素は最大 1 回だけ比較・コピーされ、
    両リストの合計要素数は n であるため。
    """
    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
 
 
def verify_merge_sort() -> None:
    """マージソートの正当性と計算量を検証する。"""
    import random
    import time
 
    sizes = [1000, 2000, 4000, 8000, 16000]
    print("=== マージソートの計算量検証 ===")
    print(f"{'n':>8} | {'時間(ms)':>10} | {'比率':>8} | {'想定される比率':>14}")
    print("-" * 50)
 
    prev_time = None
    for n in sizes:
        arr = list(range(n))
        random.shuffle(arr)
 
        start = time.perf_counter()
        merge_sort(arr)
        elapsed = (time.perf_counter() - start) * 1000
 
        if prev_time and prev_time > 0:
            ratio = elapsed / prev_time
            # O(n log n) の場合、n を 2 倍にすると
            # 2n log(2n) / (n log n) = 2(1 + log2/logn) ≈ 2+ (n が大きいとき)
            print(f"{n:>8} | {elapsed:>10.2f} | {ratio:>8.2f} | ~2.0-2.3")
        else:
            print(f"{n:>8} | {elapsed:>10.2f} | {'---':>8} | ---")
 
        prev_time = elapsed
 
 
if __name__ == "__main__":
    verify_merge_sort()

"""
マスター定理の適用例を体系的に示す。
各例で a, b, f(n) を特定し、どのケースに該当するかを判定する。
"""
 
import math
 
 
def master_theorem_analyze(
    a: int, b: int, f_desc: str, f_degree: float, algorithm: str
) -> None:
    """マスター定理によるケース判定を行う。
 
    Args:
        a: 再帰呼び出し回数
        b: 問題サイズの縮小率
        f_desc: f(n) の説明文字列
        f_degree: f(n) が Theta(n^f_degree) であるとき、その次数
        algorithm: アルゴリズム名
    """
    critical_exp = math.log(a) / math.log(b)  # log_b(a)
    print(f"--- {algorithm} ---")
    print(f"  漸化式: T(n) = {a}T(n/{b}) + {f_desc}")
    print(f"  a={a}, b={b}, n^(log_{b}({a})) = n^{critical_exp:.3f}")
    print(f"  f(n) = {f_desc} → 次数 {f_degree}")
 
    if f_degree < critical_exp:
        print(f"  f(n) の次数 {f_degree} < {critical_exp:.3f} → Case 1")
        print(f"  T(n) = Theta(n^{critical_exp:.3f})")
    elif abs(f_degree - critical_exp) < 0.001:
        print(f"  f(n) の次数 {f_degree} ≈ {critical_exp:.3f} → Case 2")
        print(f"  T(n) = Theta(n^{critical_exp:.3f} * log n)")
    else:
        print(f"  f(n) の次数 {f_degree} > {critical_exp:.3f} → Case 3")
        print(f"  T(n) = Theta({f_desc})")
    print()
 
 
def main() -> None:
    print("=== マスター定理の適用例集 ===\n")
 
    # 例1: マージソート
    master_theorem_analyze(2, 2, "n", 1.0, "マージソート")
 
    # 例2: 二分探索
    master_theorem_analyze(1, 2, "1", 0.0, "二分探索")
 
    # 例3: カラツバ乗算
    master_theorem_analyze(3, 2, "n", 1.0, "カラツバ乗算")
 
    # 例4: ストラッセン行列乗算
    master_theorem_analyze(7, 2, "n^2", 2.0, "ストラッセン行列乗算")
 
    # 例5: 二分木走査
    master_theorem_analyze(2, 2, "1", 0.0, "二分木走査")
 
    # 例6: T(n) = 4T(n/2) + n^2
    master_theorem_analyze(4, 2, "n^2", 2.0, "4T(n/2) + n^2")
 
    # 例7: T(n) = 4T(n/2) + n^3
    master_theorem_analyze(4, 2, "n^3", 3.0, "4T(n/2) + n^3")
 
    # 例8: クイックセレクト（平均）
    master_theorem_analyze(1, 2, "n", 1.0, "クイックセレクト(平均)")
 
 
if __name__ == "__main__":
    main()

"""
置換法でよくある間違いを示す。
"""
 
# 間違い1: 帰納法の仮定を「弱すぎる」形で置く
#
# 予想: T(n) = O(n) で T(n) = 2T(n/2) + n を証明しようとする
#
# T(n) = 2T(n/2) + n
#      <= 2 * c * (n/2) + n
#      = cn + n
#      = (c+1)n
#      ≠ cn   ← c が「育ってしまう」ため証明できない
#
# → これは正しい。T(n) = Θ(n log n) であって O(n) ではないから。
 
# 間違い2: 低次項を無視して「うまくいった」と誤認する
#
# 予想: T(n) <= cn で T(n) = T(n/2) + T(n/2) + 1 を証明
#
# T(n) <= c(n/2) + c(n/2) + 1 = cn + 1  ← 「ほぼ cn」だが cn 以下ではない！
#
# 正しい対処: T(n) <= cn - d とより強い仮定を置く
# T(n) <= c(n/2) - d + c(n/2) - d + 1 = cn - 2d + 1 <= cn - d (d >= 1)

def factorial(n: int) -> int:
    """階乗を再帰的に計算する。T(n) = T(n-1) + O(1) → O(n)
 
    なぜ O(n) か: 再帰の深さが n で、各レベルのコストが O(1) であるため。
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
 
# 検証
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120
assert factorial(10) == 3628800

def selection_sort(arr: list[int]) -> list[int]:
    """選択ソート。T(n) = T(n-1) + O(n) → O(n^2)
 
    なぜ O(n^2) か: 各ステップで残り要素から最小値を見つけるのに O(n)、
    それを n 回繰り返すため。漸化式を展開すると
    T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = Θ(n^2)。
    """
    arr = arr[:]
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
 
 
# 検証
assert selection_sort([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5]
assert selection_sort([]) == []
assert selection_sort([1]) == [1]

def binary_search(arr: list[int], target: int) -> int:
    """二分探索。T(n) = T(n/2) + O(1) → O(log n)
 
    なぜ O(log n) か: 各ステップで探索範囲が半分になり、
    範囲が 1 になるまで log₂n 回の比較で済むため。
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
 
 
# 検証
arr = [1, 3, 5, 7, 9, 11, 13]
assert binary_search(arr, 7) == 3
assert binary_search(arr, 1) == 0
assert binary_search(arr, 13) == 6
assert binary_search(arr, 4) == -1

def power(x: float, n: int) -> float:
    """繰り返し二乗法。T(n) = T(n/2) + O(1) → O(log n)
 
    なぜ O(log n) か: 指数を 2 で割っていくため、再帰の深さは log₂n。
    各レベルでは乗算 1 回（O(1)）のみ。
 
    x^n = (x^(n/2))^2       (n が偶数)
    x^n = x * (x^(n-1/2))^2 (n が奇数)
    """
    if n == 0:
        return 1
    if n < 0:
        return 1 / power(x, -n)
    if n % 2 == 0:
        half = power(x, n // 2)
        return half * half
    else:
        return x * power(x, n - 1)
 
 
# 検証
assert power(2, 10) == 1024
assert power(3, 0) == 1
assert abs(power(2, -1) - 0.5) < 1e-10

def fibonacci_naive(n: int) -> int:
    """素朴なフィボナッチ。T(n) = T(n-1) + T(n-2) + O(1) → O(phi^n)
 
    なぜ指数時間か: 再帰木の各ノードが 2 つの子を持ち、
    深さ n まで「ほぼ」完全二分木になるため。正確には黄金比
    phi = (1 + sqrt(5)) / 2 ≈ 1.618 のべき乗で増加する。
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
 
 
def fibonacci_dp(n: int) -> int:
    """動的計画法によるフィボナッチ。O(n) 時間、O(1) 空間。
 
    メモ化や DP テーブルで重複計算を排除することで、
    O(phi^n) → O(n) に改善される。
    """
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr
 
 
# 検証
for i in range(10):
    assert fibonacci_naive(i) == fibonacci_dp(i)

def hanoi(n: int, source: str = "A", target: str = "C", auxiliary: str = "B") -> int:
    """ハノイの塔。T(n) = 2T(n-1) + O(1) → O(2^n)
 
    なぜ O(2^n) か: n 枚を移動するには、上の n-1 枚を 2 回移動し、
    さらに最大の円盤を 1 回移動する。
    T(n) = 2T(n-1) + 1 → T(n) = 2^n - 1。
 
    Returns:
        移動回数
    """
    if n == 0:
        return 0
    moves = 0
    moves += hanoi(n - 1, source, auxiliary, target)
    moves += 1  # 最大の円盤を移動
    moves += hanoi(n - 1, auxiliary, target, source)
    return moves
 
 
# 検証: T(n) = 2^n - 1
for n in range(1, 15):
    assert hanoi(n) == 2**n - 1, f"n={n}: {hanoi(n)} != {2**n - 1}"
 
print("ハノイの塔の移動回数:")
for n in [1, 5, 10, 15, 20]:
    print(f"  n={n:>2}: {2**n - 1:>8} 回")

"""
マスター定理の「ギャップケース」に陥る例。
"""
 
# BAD: T(n) = 2T(n/2) + n log n にマスター定理を直接適用しようとする
#
# a=2, b=2 → n^(log_2(2)) = n^1 = n
# f(n) = n log n
#
# Case 2 に該当するか？ → Case 2 は f(n) = Θ(n^(log_b(a))) を要求。
#   n log n ≠ Θ(n) なので Case 2 ではない。
#
# Case 3 に該当するか？ → Case 3 は f(n) = Ω(n^(1+ε)) を要求。
#   n log n = O(n^(1+ε)) for any ε > 0 なので Case 3 でもない。
#
# → 標準のマスター定理は適用不可（ギャップケース）
# → 拡張マスター定理を適用: f(n) = Θ(n log^k n) で k=1 のとき
#   T(n) = Θ(n log^(k+1) n) = Θ(n log^2 n)
#
# GOOD: 適用前に必ず 3 ケースのどれに該当するか確認し、
#        どれにも該当しない場合は再帰木法や Akra-Bazzi 定理を使う。

"""
再帰の「深さ」と「呼び出し総数」は別の概念である。
"""
 
# BAD: 「二分再帰だから O(log n)」と誤解する
def count_all(n: int) -> int:
    """T(n) = T(n-1) + T(n-2) + O(1)
 
    誤った推論: 「再帰が 2 つに分かれるから O(log n)」
    正しい分析: 深さは O(n)、呼び出し回数は O(φ^n)
    """
    if n <= 0:
        return 0
    return 1 + count_all(n - 1) + count_all(n - 2)
 
 
# GOOD: 深さと呼び出し回数を区別して分析する
#
#   再帰木の深さ: 最も深いパスの長さ → スタック使用量に影響
#   呼び出し回数: 全ノード数 → 時間計算量に影響
#
#   例: フィボナッチ再帰
#     深さ: O(n) — 左端のパスが n → n-1 → n-2 → ... → 0
#     呼び出し回数: O(φ^n) — ほぼ完全二分木に近い構造

"""
平均ケースは確率分布に基づく期待値であり、
「よくある入力」での性能とは必ずしも一致しない。
"""
 
# BAD: 「クイックソートの平均 O(n log n) だから、
#        ほぼすべての入力で O(n log n) になる」と誤解
 
# 正しい理解:
# 1. 平均ケースは「すべてのサイズ n の入力が等確率で出現する」
#    という仮定のもとでの期待値
# 2. 実際のアプリケーションでは入力に偏りがある場合がある
#    例: ほぼソート済みデータが頻繁に入力されるログ処理システム
# 3. 敵対的入力（adversarial input）が存在する環境では、
#    最悪ケースの保証が必要
 
# GOOD: 入力の分布を考慮してアルゴリズムを選択する
# - ランダムな入力が保証される → 平均ケースで評価可能
# - 敵対的入力の可能性あり → 最悪ケースの保証が必要
# - 特定のパターンが多い → そのパターンでの性能を個別に評価

"""
漸近的に同等でも、再帰のオーバーヘッドが定数係数に影響する。
"""
 
import time
 
 
def sum_recursive(n: int) -> int:
    """再帰版の合計。時間計算量: O(n)。"""
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)
 
 
def sum_iterative(n: int) -> int:
    """反復版の合計。時間計算量: O(n)。"""
    total = 0
    for i in range(1, n + 1):
        total += i
    return total
 
 
def compare_overhead() -> None:
    """再帰と反復のオーバーヘッド差を測定する。
 
    漸近記法では両方 O(n) だが、再帰版は関数呼び出しのオーバーヘッド
    （スタックフレームの生成・破棄）により定数係数が大きくなる。
    """
    import sys
    sys.setrecursionlimit(20000)
 
    n = 10000
    start = time.perf_counter()
    result_rec = sum_recursive(n)
    time_rec = time.perf_counter() - start
 
    start = time.perf_counter()
    result_iter = sum_iterative(n)
    time_iter = time.perf_counter() - start
 
    assert result_rec == result_iter
 
    print(f"n = {n}")
    print(f"  再帰版: {time_rec * 1000:.2f} ms")
    print(f"  反復版: {time_iter * 1000:.2f} ms")
    print(f"  比率: {time_rec / time_iter:.1f}x")
    print(f"  → 漸近的には同じ O(n) だが、定数係数が異なる")
 
 
if __name__ == "__main__":
    compare_overhead()

"""
小さな入力サイズでは、漸近的に「劣る」アルゴリズムが
漸近的に「優れる」アルゴリズムより高速になるケースを示す。
 
なぜこの現象が起きるか:
O(n^2) アルゴリズムの定数係数が O(n log n) アルゴリズムより
十分小さい場合、n が小さいうちは定数係数の差が支配する。
"""
 
import time
import random
 
 
def insertion_sort(arr: list[int]) -> list[int]:
    """挿入ソート。最悪 O(n^2) だが定数係数が小さい。"""
    arr = arr[:]
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
 
 
def merge_sort_full(arr: list[int]) -> list[int]:
    """マージソート。O(n log n) だが定数係数がやや大きい。"""
    if len(arr) <= 1:
        return arr[:]
    mid = len(arr) // 2
    left = merge_sort_full(arr[:mid])
    right = merge_sort_full(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
 
 
def find_crossover_point() -> None:
    """挿入ソートとマージソートの交差点を実験的に見つける。
 
    想定される結果: n が 20-50 程度で交差する。
    これが Tim Sort（Python の組み込みソート）が小さな部分配列に
    挿入ソートを使う理由である。
    """
    print("=== 小さな入力サイズでの比較 ===")
    print(f"{'n':>6} | {'挿入ソート(ms)':>14} | {'マージソート(ms)':>14} | {'速い方':>8}")
    print("-" * 55)
 
    trials = 1000
    for n in [5, 10, 15, 20, 30, 50, 100, 200, 500]:
        # 挿入ソートの計測
        total_ins = 0
        for _ in range(trials):
            arr = random.sample(range(n * 10), n)
            start = time.perf_counter()
            insertion_sort(arr)
            total_ins += time.perf_counter() - start
 
        # マージソートの計測
        total_merge = 0
        for _ in range(trials):
            arr = random.sample(range(n * 10), n)
            start = time.perf_counter()
            merge_sort_full(arr)
            total_merge += time.perf_counter() - start
 
        ins_ms = total_ins / trials * 1000
        merge_ms = total_merge / trials * 1000
        winner = "挿入" if ins_ms < merge_ms else "マージ"
        print(f"{n:>6} | {ins_ms:>14.4f} | {merge_ms:>14.4f} | {winner:>8}")
 
    print()
    print("  → n が小さいとき、O(n^2) の挿入ソートが O(n log n) のマージソートに勝つ。")
    print("    これは漸近記法が定数係数を無視することの実用的帰結である。")
 
 
if __name__ == "__main__":
    find_crossover_point()

"""
ベースケースのコストが O(1) でない場合、漸化式の解が変わることを示す。
"""
 
 
def matrix_multiply_recursive(
    A: list[list[float]], B: list[list[float]], n: int
) -> list[list[float]]:
    """再帰的行列乗算（単純な分割統治）。
 
    ベースケースが 1x1 行列のとき: T(1) = O(1)
    → T(n) = 8T(n/2) + O(n^2) → O(n^3)
 
    もしベースケースを k×k（k は定数）にして直接計算すると:
    T(k) = O(k^3) ≈ O(1)  （k が定数なら）
    漸近的な結果は変わらないが、定数係数が改善される。
 
    なぜこれが重要か: 実装では再帰のベースケースを適切に設定することで、
    関数呼び出しのオーバーヘッドを削減できる。ストラッセンのアルゴリズムでも、
    n が十分小さくなったら通常の O(n^3) 行列乗算に切り替える。
    """
    if n == 1:
        return [[A[0][0] * B[0][0]]]
 
    mid = n // 2
 
    # 部分行列の抽出（簡略化のためスライスを使用）
    A11 = [row[:mid] for row in A[:mid]]
    A12 = [row[mid:] for row in A[:mid]]
    A21 = [row[:mid] for row in A[mid:]]
    A22 = [row[mid:] for row in A[mid:]]
 
    B11 = [row[:mid] for row in B[:mid]]
    B12 = [row[mid:] for row in B[:mid]]
    B21 = [row[:mid] for row in B[mid:]]
    B22 = [row[mid:] for row in B[mid:]]
 
    # 8 回の再帰呼び出し
    C11 = matrix_add(
        matrix_multiply_recursive(A11, B11, mid),
        matrix_multiply_recursive(A12, B21, mid),
    )
    C12 = matrix_add(
        matrix_multiply_recursive(A11, B12, mid),
        matrix_multiply_recursive(A12, B22, mid),
    )
    C21 = matrix_add(
        matrix_multiply_recursive(A21, B11, mid),
        matrix_multiply_recursive(A22, B21, mid),
    )
    C22 = matrix_add(
        matrix_multiply_recursive(A21, B12, mid),
        matrix_multiply_recursive(A22, B22, mid),
    )
 
    # 結果の統合
    result = []
    for i in range(mid):
        result.append(C11[i] + C12[i])
    for i in range(mid):
        result.append(C21[i] + C22[i])
    return result
 
 
def matrix_add(
    A: list[list[float]], B: list[list[float]]
) -> list[list[float]]:
    """行列の加算。O(n^2)。"""
    n = len(A)
    return [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
 
 
def verify_recursive_matrix_multiply() -> None:
    """再帰的行列乗算の正当性を検証する。"""
    A = [[1, 2], [3, 4]]
    B = [[5, 6], [7, 8]]
    C = matrix_multiply_recursive(A, B, 2)
    # 期待値: [[19, 22], [43, 50]]
    assert C == [[19, 22], [43, 50]], f"Got {C}"
 
    # 4x4 行列のテスト
    A4 = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
    B4 = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
    C4 = matrix_multiply_recursive(A4, B4, 4)
    assert C4 == B4, "単位行列との積は元の行列に等しいはず"
 
    print("再帰的行列乗算: 全テスト通過")
 
 
if __name__ == "__main__":
    verify_recursive_matrix_multiply()

# (a) 最大値を再帰的に求める
def find_max(arr: list[int], n: int) -> int:
    if n == 1:
        return arr[0]
    return max(arr[n - 1], find_max(arr, n - 1))
 
 
# (b) 配列の合計を分割統治で求める
def divide_sum(arr: list[int], left: int, right: int) -> int:
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    return divide_sum(arr, left, mid) + divide_sum(arr, mid + 1, right)
 
 
# (c) べき乗を再帰的に計算する（非効率版）
def power_naive(x: float, n: int) -> float:
    if n == 0:
        return 1
    return x * power_naive(x, n - 1)

def linear_search_first_even(arr: list[int]) -> int:
    """配列から最初の偶数を見つけて返す。見つからなければ -1。"""
    for i, val in enumerate(arr):
        if val % 2 == 0:
            return val
    return -1

class BinaryCounter:
    """k ビットの二進カウンタ。"""
 
    def __init__(self, k: int) -> None:
        self.bits = [0] * k
        self.k = k
 
    def increment(self) -> int:
        """カウンタを 1 増やす。ビット反転回数を返す。"""
        flips = 0
        i = 0
        while i < self.k and self.bits[i] == 1:
            self.bits[i] = 0  # 桁上がり
            flips += 1
            i += 1
        if i < self.k:
            self.bits[i] = 1
            flips += 1
        return flips