输入：两个正整数 a, b
输出：gcd(a, b)

步骤：
1. 如果 b = 0，返回 a
2. 否则，返回 gcd(b, a mod b)

def linear_search(arr, target):
    for i in range(len(arr)):      # n次比较
        if arr[i] == target:
            return i
    return -1

def linear_search(arr, target):
    """时间复杂度: O(n), 空间复杂度: O(1)"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

def binary_search(arr, target):
    """
    前提：arr已排序
    时间复杂度: O(log n), 空间复杂度: O(1)
    """
    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

def bubble_sort(arr):
    """
    时间复杂度: O(n²), 空间复杂度: O(1)
    稳定排序
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 优化：如果没有交换，提前终止
            break

def insertion_sort(arr):
    """
    时间复杂度: O(n²), 空间复杂度: O(1)
    稳定排序，对小数组高效
    """
    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

def merge_sort(arr):
    """
    时间复杂度: O(n log n), 空间复杂度: O(n)
    稳定排序
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    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 quick_sort(arr):
    """
    平均时间复杂度: O(n log n)
    最坏时间复杂度: O(n²)（当pivot选择不当时）
    空间复杂度: O(log n)（递归栈）
    不稳定排序
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    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 quick_sort(left) + middle + quick_sort(right)

# Python内置排序（TimSort，混合归并排序和插入排序）
sorted_list = sorted(my_list)

# 二分搜索
import bisect
index = bisect.bisect_left(sorted_list, target)

# 堆操作
import heapq
heapq.heappush(heap, item)
heapq.heappop(heap)

"""
算法复杂度可视化：比较不同增长率的函数
"""

import math
import matplotlib.pyplot as plt


def plot_complexities():
    """绘制常见复杂度函数的增长曲线"""
    n_values = list(range(1, 101))
    
    complexities = {
        'O(1)': [1] * len(n_values),
        'O(log n)': [math.log2(n) for n in n_values],
        'O(n)': n_values.copy(),
        'O(n log n)': [n * math.log2(n) for n in n_values],
        'O(n²)': [n ** 2 for n in n_values],
        'O(2ⁿ)': [min(2 ** n, 10**6) for n in n_values],  # 限制最大值以便显示
    }
    
    plt.figure(figsize=(12, 8))
    
    for name, values in complexities.items():
        plt.plot(n_values, values, label=name, linewidth=2)
    
    plt.xlabel('输入规模 n', fontsize=12)
    plt.ylabel('操作次数', fontsize=12)
    plt.title('算法复杂度比较', fontsize=14)
    plt.legend(fontsize=11)
    plt.grid(True, alpha=0.3)
    plt.ylim(0, 1000)  # 限制y轴范围以便观察
    plt.tight_layout()
    plt.savefig('complexity_comparison.png', dpi=150)
    plt.show()
    
    print("复杂度比较图已保存为 complexity_comparison.png")


def compare_sorting_algorithms():
    """比较不同排序算法的实际运行时间"""
    import random
    import time
    
    def generate_random_array(size):
        return [random.randint(0, 10000) for _ in range(size)]
    
    def benchmark(func, arr):
        start = time.perf_counter()
        func(arr.copy())
        end = time.perf_counter()
        return end - start
    
    sizes = [100, 500, 1000, 2000, 5000]
    
    print("排序算法性能比较（秒）:")
    print(f"{'大小':>8} {'冒泡':>10} {'插入':>10} {'归并':>10} {'快速':>10}")
    print("-" * 50)
    
    for size in sizes:
        arr = generate_random_array(size)
        
        bubble_time = benchmark(bubble_sort_impl, arr)
        insert_time = benchmark(insertion_sort_impl, arr)
        merge_time = benchmark(merge_sort_impl, arr)
        quick_time = benchmark(quick_sort_impl, arr)
        
        print(f"{size:>8} {bubble_time:>10.6f} {insert_time:>10.6f} "
              f"{merge_time:>10.6f} {quick_time:>10.6f}")


# 排序算法的实现（用于基准测试）
def bubble_sort_impl(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def insertion_sort_impl(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


def merge_sort_impl(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_impl(arr[:mid])
    right = merge_sort_impl(arr[mid:])
    return merge_impl(left, right)


def merge_impl(left, right):
    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 quick_sort_impl(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    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 quick_sort_impl(left) + middle + quick_sort_impl(right)


if __name__ == "__main__":
    plot_complexities()
    print()
    compare_sorting_algorithms()

"""
二分搜索及其变体的完整实现
"""


def binary_search_exact(arr, target):
    """
    标准二分搜索：查找精确匹配
    
    返回: 目标索引，未找到返回-1
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


def binary_search_lower_bound(arr, target):
    """
    查找下界：第一个大于等于target的元素位置
    
    返回: 下界索引
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left


def binary_search_upper_bound(arr, target):
    """
    查找上界：第一个大于target的元素位置
    
    返回: 上界索引
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left


def binary_search_first_occurrence(arr, target):
    """
    查找目标第一次出现的位置（数组可能有重复元素）
    
    返回: 第一次出现的索引，未找到返回-1
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 继续在左半部分查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result


def binary_search_last_occurrence(arr, target):
    """
    查找目标最后一次出现的位置（数组可能有重复元素）
    
    返回: 最后一次出现的索引，未找到返回-1
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # 继续在右半部分查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result


def demonstrate_binary_search_variants():
    """演示二分搜索的各种变体"""
    
    arr = [1, 2, 2, 2, 3, 4, 5, 5, 6, 7]
    target = 2
    
    print(f"数组: {arr}")
    print(f"目标: {target}")
    print()
    
    exact = binary_search_exact(arr, target)
    print(f"精确匹配索引: {exact}")
    
    lower = binary_search_lower_bound(arr, target)
    print(f"下界索引（第一个≥{target}）: {lower}")
    
    upper = binary_search_upper_bound(arr, target)
    print(f"上界索引（第一个>{target}）: {upper}")
    
    first = binary_search_first_occurrence(arr, target)
    print(f"第一次出现: {first}")
    
    last = binary_search_last_occurrence(arr, target)
    print(f"最后一次出现: {last}")
    
    # 验证
    print("\n验证:")
    print(f"  arr[{lower}:{upper}] = {arr[lower:upper]}")
    print(f"  所有元素都等于{target}: {all(x == target for x in arr[lower:upper])}")


def find_peak_element(arr):
    """
    查找峰值元素：比邻居都大的元素
    
    使用二分搜索思想，时间复杂度 O(log n)
    
    返回: 峰值索引
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] < arr[mid + 1]:
            left = mid + 1  # 峰值在右边
        else:
            right = mid  # 峰值在左边或就是mid
    
    return left


if __name__ == "__main__":
    demonstrate_binary_search_variants()
    
    print("\n" + "=" * 50)
    print("峰值查找示例:")
    arr = [1, 2, 3, 1, 2, 3, 1]
    peak_idx = find_peak_element(arr)
    print(f"数组: {arr}")
    print(f"峰值索引: {peak_idx}, 峰值: {arr[peak_idx]}")

"""
递归算法与记忆化优化
"""

import time
from functools import lru_cache


# --- 斐波那契数列 ---

def fibonacci_naive(n):
    """
     naive递归：指数时间复杂度 O(2^n)
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)


@lru_cache(maxsize=None)
def fibonacci_memo(n):
    """
    记忆化递归：线性时间复杂度 O(n)
    """
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)


def fibonacci_iterative(n):
    """
    迭代方法：线性时间复杂度 O(n)，常数空间 O(1)
    """
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr


# --- 爬楼梯问题 ---

def climb_stairs_naive(n):
    """
    每次可以爬1或2阶，爬到第n阶有多少种方法？
    naive递归：指数时间
    """
    if n <= 2:
        return n
    return climb_stairs_naive(n - 1) + climb_stairs_naive(n - 2)


@lru_cache(maxsize=None)
def climb_stairs_memo(n):
    """记忆化版本"""
    if n <= 2:
        return n
    return climb_stairs_memo(n - 1) + climb_stairs_memo(n - 2)


# --- 硬币找零问题 ---

def coin_change_greedy(coins, amount):
    """
    贪心算法：不一定得到最优解
    
    返回: 最少硬币数，无法找零返回-1
    """
    coins.sort(reverse=True)
    count = 0
    remaining = amount
    
    for coin in coins:
        while remaining >= coin:
            remaining -= coin
            count += 1
    
    return count if remaining == 0 else -1


def coin_change_dp(coins, amount):
    """
    动态规划：保证最优解
    
    时间复杂度: O(amount * len(coins))
    空间复杂度: O(amount)
    
    返回: 最少硬币数，无法找零返回-1
    """
    # dp[i] 表示凑成金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1


def demonstrate_recursion_optimization():
    """演示递归优化的效果"""
    
    n = 30
    
    print(f"斐波那契数列 F({n}):")
    
    # Naive递归（仅对小n执行，否则太慢）
    if n <= 30:
        start = time.perf_counter()
        result_naive = fibonacci_naive(n)
        time_naive = time.perf_counter() - start
        print(f"  Naive递归: {result_naive} (耗时: {time_naive:.4f}s)")
    
    # 记忆化递归
    start = time.perf_counter()
    result_memo = fibonacci_memo(n)
    time_memo = time.perf_counter() - start
    print(f"  记忆化递归: {result_memo} (耗时: {time_memo:.6f}s)")
    
    # 迭代
    start = time.perf_counter()
    result_iter = fibonacci_iterative(n)
    time_iter = time.perf_counter() - start
    print(f"  迭代方法:   {result_iter} (耗时: {time_iter:.6f}s)")
    
    print(f"\n验证一致性: {result_memo == result_iter}")
    
    # 清除缓存
    fibonacci_memo.cache_clear()


def demonstrate_coin_change():
    """演示硬币找零问题"""
    
    coins = [25, 10, 5, 1]  # 美分硬币
    amount = 63
    
    print(f"\n硬币找零问题:")
    print(f"  硬币面额: {coins}")
    print(f"  目标金额: {amount}")
    
    greedy_result = coin_change_greedy(coins.copy(), amount)
    dp_result = coin_change_dp(coins, amount)
    
    print(f"  贪心算法: {greedy_result} 枚硬币")
    print(f"  动态规划: {dp_result} 枚硬币")
    
    # 展示贪心不是最优的例子
    print("\n  贪心非最优的例子:")
    coins_special = [1, 3, 4]
    amount_special = 6
    
    greedy_special = coin_change_greedy(coins_special.copy(), amount_special)
    dp_special = coin_change_dp(coins_special, amount_special)
    
    print(f"    硬币面额: {coins_special}")
    print(f"    目标金额: {amount_special}")
    print(f"    贪心算法: {greedy_special} 枚（4+1+1）")
    print(f"    动态规划: {dp_special} 枚（3+3）← 更优")


if __name__ == "__main__":
    demonstrate_recursion_optimization()
    demonstrate_coin_change()