算法设计：感觉不如OI Wiki
课程考试可能是为数不多的不允许使用课本外的算法的，所以真不如OI Wiki
课本：算法设计与分析 第二版 黄宇 南京大学编著 机械工业出版社

课程大纲

针对小朋友开设的算法课👶♿♿♿，老奶奶推轮椅都能学会的知识👵♿♿♿

  • 算法基本概念
  • 时间复杂度的计算
  • 排序
    • $QUICK-SORT: O(n \log n)$
      • $PARTITION: O(n)$
    • $MERGE-SORT: O(n \log n)$
      • $MERGE: O(n)$
    • 下界证明：决策树的叶节点对应于排序的结果，而排序的结果为输入元素的某一种排列，所以排列的结果有$n!$种，决策树的叶节点至少有$n!$。记高度$h$，叶节点个数$L$，那么$n! \leq L \leq 2^h$，因此$h \geq \log (n!) = \Omega(n \log n)$。由树高代表了最坏情况时间复杂度的下解则得之。
  • 选择
    • $PARTITION + SELECT: average\ O(n)\ and\ worst\ O(n^2)$
    • 每五个一组，取中位数，递归：$SELECT-WLINEAR: worst\ O(n)$
  • 查找
    • $BINARY-SEARCH: O(\log n)$
    • 由需要平衡二叉搜索树，推到红黑树
  • 堆与偏序关系
    • $MAKE: O(n)$
    • $REPAIR: O(\log n)$
    • 高度为$h$的节点个数为$\lceil \frac{n}{2^{h+1}} \rceil$

  • 并查集

    • 加权并
      find(x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

    • 路径压缩查
      void unite(size_t x, size_t y) {
      x = find(x), y = find(y);
      if (x == y) return;
      if (size[x] < size[y]) swap(x, y);
      pa[y] = x;
      size[x] += size[y];
      }

    • 对于包含$n$个元素的并查集，执行长度为$l$的加权并和路径压缩查，最坏情况时间复杂度为$O((n+l) \log^* n) \approx O(n+l)$
  • 哈希表和查找
    • 封闭寻址，查找代价：$O(1 + \alpha) , \alpha = \frac{n}{m}$
    • 开放寻址，不成功的寻找代价：$O(\frac{1}{1 - \alpha})$
    • 开放寻址，成功寻址的平均代价：$O(\frac{1}{\alpha} \ln \frac{1}{1-\alpha})$
  • 摊销分析
  • 对手论证
  • 图遍历
    • 图论部分的课程几乎均与图论与算法课程内容重合
    • 不行，这托石不能我一个人吃
    • 不是哥们，太丑陋了

图的深搜、广搜

首先需要对课本的抽象内容进行翻译，读了二十年书没见过这种表述：

  • TE：树边
  • BE：后向边
  • DE：前向边
  • CE：除此以外的边
  • 遍历时间：时间戳
    • 被发现：DFS进入
    • 遍历结束：DFS离开
    • 活动区间：代码执行时
  • 尽头：深搜时最后得到的没有出度的点
  • 逻辑尽头：所有的后继节点已经被DFS执行完毕
  • 任务：点
  • 任务的执行时长：点具有权重
  • 开始时间：sum
  • 结束时间：sum + weight

广搜SCC思想：搜索，先结束先入栈，然后翻转图，此时“起点”变“尽头”，“尽头”变“起点”，逻辑排序反转，按照栈中点的出战顺序即可逐个得到SCC。

难题 & 思考

关于堆：14.4

请证明在一个有n个节点的堆中，所有节点的高度之和最多为n - 1，并说明在何种情况下所有节点的高度之和为n - 1。

Std::Prove

首先，对于一个任意的堆，其所有子堆中至多只能有一个是非完美堆。
而对于完美堆，我们可以轻松计算出所有节点的高度和，并与节点个数进行比较。
凭此进行递归即可证。

然而，给出的标准证明并没有解释为什么这么做，这就像是一个非常tricky的奇思妙想。这在数学证明中是令人不快的天才的想法。
深入考察堆的结构和性质，我给出了如下较为严谨的证明，其更加自然（就是我比较菜吧）

My::Prove&Thinking

证明：考虑所有点的高度和与边之间的数量对应关系，原命题转化为证明所有点高度和不大于边数量。

引理1：在堆的任意一层中，将该层节点按照其下标从小到大排序，考察它们形成的高度序列，必然呈现如下二者情况之一（定义NULL节点的高度为-1）：

  • a) 若干个i + 1，之后是若干个i
  • b) 全为i

引理1的证明：该层为

  • 深度为0的层
  • 堆是完美二叉堆
    的情况时显然为情况b)。
    其余情况时，
  • 若该层有任意两个节点的高度相差大于1，那么不符合这是一个堆。
  • 若该层有任意两个节点u,v具有相同的高度，但是在这两个节点之间有具有不同高度值的节点$w$，那么考察该堆的深度最大的层；
    • w的高度较小，那么节点u,v所对应的叶子节点下标之间有一段空缺，这违反了堆的存储是以数组连续存储的。
    • w的高度较大，那么节点w所对应的叶子节点下标之前有一段空缺，这违反了堆的存储是以数组连续存储的。
      因此剩余的情况必然符合情况a)或者b)。
      引理得证。

引理2：对于任意堆，任意节点的高度必然为其左孩子的高度加一（定义NULL节点的高度为-1）。

由引理1和节点高度的计算公式立得之。

引理3：定义一个点为好点，当且仅当这个点满足：其左孩子的高度大于右孩子的高度（定义NULL节点的高度为-1）。对于任意堆的任一层，好点至多只能有一个。

引理3的证明：
考虑该层的下一层。在下一层中，由引理1得，相邻两个点的高度要么相等，要么左比右大1。而好点要求其左右孩子高度不相同，这样的点对在下一层中最多只有一对。因此引理3得证。当下一层满足情况的点对共享父节点时，这一层有一个好点；当下一层没有满足情况的点对或者有但是不共享父节点时，这一层没有好点。

现将所有点的高度与边建立对应关系。

  • 根节点的高度值对应其一直访问左孩子到达叶子节点的路径长度
  • 如果一个点是父节点的右孩子，那么将其高度值对应其一直访问左孩子到达叶子节点的路径长度
  • 如果一个点是父节点的左孩子，那么将其高度值对应其一直访问右孩子到达叶子节点的路径长度

现在我们来比较这个对应关系

  • 由引理2，我们可知任意点的高度 = 其一直访问左孩子到达叶子节点的路径长度。
  • 如果某一点不是好点，那么其高度 = 其一直访问右孩子到达叶子节点的路径长度是相等。
  • 如果某一点是好点，那么其高度 = 其一直访问右孩子到达叶子节点的路径长度 + 1。
    因此，考察任意一条边：
  • 如果该边在根节点一直访问右孩子到达叶子节点的路径中，那么这条边不在这个对应关系中
  • 否则，该边必被对应且仅被对应一次，对应的点满足以下两种情况之一：
    • 一直访问左孩子到达叶子节点的节点的路径中有该边，且该点为其父节点的右孩子
    • 一直访问右孩子到达叶子节点的节点的路径中有该边，且该点为其父节点的左孩子，或者该点为根节点。
      故我们现在仅需比较好点的数量和根节点一直访问右孩子到达叶子节点的路径长度。在这个点高度-边的对应关系中，根节点的高度已经被相等数量的边对应，因此只需要考虑非根层的好点数量；由引理3，好点的数量至多为堆的高度，而这是包括根节点所在层的，因此非根层的好点数量至多为堆的高度 - 1，而根节点一直访问右孩子到达叶子节点的路径长度恰为堆的高度 - 1，因此所有点高之和不大于n - 1。