- 高级算法的分析与设计
  - 上次课程回顾
    - 算法定义：用计算机解决问题的思路和方法
    - 算法特性介绍
  - 本次课程内容
    - 分治法
      - 定义：将大问题分解为小问题，逐个解决
      - 起源：源自军事策略
      - 步骤
        - Divide：将大问题分解为子问题
        - Conquer：解决子问题
        - Combine：合并子问题的解
      - 应用实例
        - 归并排序
          - 分解数组为子数组
          - 递归排序子数组
          - 合并有序子数组
        - 二分查找
          - 在有序数组中查找目标值
          - 比较目标值与中位数
          - 根据比较结果缩小查找范围
          - 时间复杂度：Θ(logN)
    - 分治法的时间复杂度分析
      - 表达式：T(n) = T(n/2) + Θ(1)
      - 主方法应用
        - 比较 N^logB(A) 和 f(n)
        - 结论：时间复杂度为 Θ(logN)
    - 分治法在求幂运算中的应用
      - 问题：计算 A 的 N 次幂
      - 常规方法：循环 N 次，时间复杂度 Θ(N)
      - 分治法优化
        - 思路：A^N = A^(N/2) * A^(N/2)
        - 奇偶情况讨论
          - 偶数：A^N = A^(N/2) * A^(N/2)
          - 奇数：A^N = A^(N/2) * A^(N/2) * A
        - 时间复杂度：Θ(logN)
    - 生日悖论问题
      - 确定性问题
        - 房间人数：366人
        - 理由：覆盖所有可能生日
      - 概率性问题
        - 条件：50% 概率有两人同一天生日
        - 结论：房间人数为 28 人