数据结构与算法分析 C 语言描述

Data Structures and Algorithm Analysis in C, Second Edition

出版社	作者	原书年份
机械工业出版社	Mark Allen Weiss	1997

Ch1. 引言

• 两个问题引入：

  • 寻找数组中第 k 大的元素
    • 第一种方法：降序排列取第 k 个元素。
    • 第二种方法：将元素依次插入一个大小为 k 的降序数组，小于末位元素则忽略，返回最后一个。
    • 最优解：第七章介绍
  • Word puzzle

• 回忆一些数学基础：

  • 几何级数、等差数列、其他常见级数的求和公式
  • 证明方法：数学归纳法、反证法、举反例法

• 递归基础：

  • 必须具备两种情况：基本情况和递归情况
  • 在不同的递归调用中，不应该做重复的事情（斐波那契数列）
  • 证明递归的正确性：使用归纳法

Ch2. 算法分析

• 引入记号：
  • O：渐进上界
  • Ω：渐进下界
  • Θ：渐进紧密界
  • o：渐进上界，但不是紧密界
  • 学会使用 \(\lim_{n \to \infty} \frac{f(n)}{g(n)}\) 判断渐进界
• 三条法则：
  • 乘法法则：\(T(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))\)
  • 加法法则：\(T(n) = O(f(n)) + O(g(n)) = O(f(n) + g(n))\)
  • 对数法则：\(\log^k N = O(N)\)