01. 算法复杂度分析

# 示例 1：O(n)
def sum_array(arr):
    total = 0
    for x in arr:          # n 次
        total += x
    return total

# 示例 2：O(n²)
def find_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):  # n * n
            print(arr[i], arr[j])

# 示例 3：O(log n)
def binary_search(arr, target):
    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

# 示例 4：O(n log n)
def efficient_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2             # O(1)
    left = efficient_sort(arr[:mid])   # T(n/2)
    right = efficient_sort(arr[mid:])  # T(n/2)
    return merge(left, right)       # O(n)
    # 递推：T(n) = 2T(n/2) + O(n) → O(n log n)

# O(1) 额外空间
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# O(n) 额外空间
def copy_double(arr):
    result = []          # 额外创建 n 个元素
    for x in arr:
        result.append(x * 2)
    return result

# O(n) 递归栈空间
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # 深度为 n 的调用栈

# O(log n) 递归栈空间（二分递归）
def fib_log_space(n):
    if n <= 1:
        return n
    return fib_log_space(n - 1) + fib_log_space(n - 2)  # 实际上为 O(n)，这里需要更准确说明

# 求以下代码时间复杂度
def foo(n):
    i = 1
    while i < n:
        i = i * 2
        print(i)
# 答案：O(log n)，因为 i 呈指数增长

# 求以下代码时间复杂度
def bar(n):
    for i in range(n):
        j = 1
        while j < n:
            j = j * 2
            print(i, j)
# 答案：O(n log n)，外层 n 次，内层 log n 次

# 空间换时间：两数之和
# 暴力 O(n²) → 哈希表 O(n)
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# 辅助空间 O(1)：返回值不计入
# 但总空间 O(n)（如果考虑输入本身的大小）
def reverse_in_place(arr: list) -> list:
    """原地反转：辅助空间 O(1)"""
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# 辅助空间 O(n) + 返回结果 O(n) = 总空间 O(n)
def reverse_copy(arr: list) -> list:
    """非原地反转：需要额外 O(n) 空间"""
    result = [0] * len(arr)
    for i in range(len(arr)):
        result[i] = arr[len(arr) - 1 - i]
    return result

# 递归栈空间常被忽视
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# 空间复杂度：O(n) — n 层递归调用栈

# 经典斐波那契：DP 表 O(n) 空间
def fib_dp(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 空间优化：只保留最后两个值 → O(1) 空间
def fib_optimized(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

# ❌ 错误：Python 字符串不可变，每次拼接都是 O(n)
def build_string(n: int) -> str:
    result = ""
    for i in range(n):
        result += str(i)  # 每次重新分配，总 O(n²)
    return result

# ✅ 正确：使用列表 + join，总 O(n)
def build_string_fast(n: int) -> str:
    parts = []
    for i in range(n):
        parts.append(str(i))
    return "".join(parts)

# ✅ 更简洁：生成器表达式
def build_string_pythonic(n: int) -> str:
    return "".join(str(i) for i in range(n))

# ❌ 假设 get 总是 O(1)，忽略了最坏情况
def count_unique_bad(arr: list) -> dict:
    counts = {}
    for item in arr:
        counts[item] = counts.get(item, 0) + 1
    # 若所有键都有相同 hash（哈希攻击），退化为链表 O(n²)
    return counts

# ✅ 使用 Python 3.7+ 的有序字典（压缩表实现，冲突概率极低）
from collections import defaultdict
def count_unique_safe(arr: list) -> dict:
    counts = defaultdict(int)
    for item in arr:
        counts[item] += 1
    return dict(counts)

# Python 默认递归深度限制 1000
def factorial_recursive(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
# factorial_recursive(10000) → RecursionError

# ✅ 尾递归优化（或通过显式栈）
def factorial_iterative(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
# O(1) 栈空间，可处理任意 n

# 场景：两数之和
# 时间换空间：O(n²) 时间，O(1) 空间
def two_sum_brute(nums: list, target: int) -> list:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# 空间换时间：O(n) 时间，O(n) 空间
def two_sum_hash(nums: list, target: int) -> list:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []