In 2025, amid all the talk about AI threats, slop set a tone that’s less fearful, more mocking. The word sends a little message to AI: when it comes to replacing human creativity, sometimes you don’t seem too superintelligent.
voidShortestPath(Graph G, int v0, ShortestPathTable &D) { final[] = FALSE; final[v0] = TRUE; D[] = G.arcs[v0][]; D[v0] = 0; for (i = 1; i < G.vexnum; ++i) { min = INFINITY; for (w = 0; w < G.vexnum; w++) if (!final[w] && D[w] < min) { min = D[w]; v = w; } final[v] = TRUE; for (w = 0; w < G.vexnum; w++) if (!final[w]) D[w] = min(D[w], min + G.arcs[v][w]); } }
Floyd 算法求全源最短路径: 注意 的意义是只经过 号顶点的路径的最小值.
第 9 章 查找
折半查找 (最坏情形下查找长度 )
1 2 3 4 5 6 7 8 9 10
intSearch_Bin(SSTable ST, KeyType key) { low = 1; high = ST.length; while (low <= high) { mid = (low + high) / 2; if (EQ(key, ST.elem[mid].key)) return mid; if (LT(key, ST.elem[mid].key)) high = mid - 1; else low = mid + 1; } return0; }
intPartition(SqList &L, int low, int high) { L.r[0] = L.r[low]; pivotkey = L.r[low].key; while (low < high) { while (low < high && L.r[high].key >= pivotkey) --high; L.r[low] = L.r[high]; while (low < high && L.r[low].key <= pivotkey) ++low; L.r[high] = L.r[low]; } L.r[low] = L.r[0]; return low; } voidQSort(SqList &L, int low, int high) { if (low < high) { pos = Partition(L, low, high); QSort(L, low, pos - 1); QSort(L, pos + 1, high); } }
选择排序
锦标赛排序
堆排序 (建堆比较次数 , 总比较次数 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
typedef SqList HeapType; voidHeapAdjust(HeapType &H, int s, int m) { rc = H.r[s]; for (j = 2 * s; j <= m; j *= 2) { if (j < m && LT(H.r[j].key, H.r[j + 1].key)) ++j; if (LQ(H.r[j].key, rc.key)) break; H.r[s] = H.r[j]; s = j; } H.r[s] = rc; } voidHeapSort(HeapType &H) { for (i = H.length / 2; i > 0; i--) HeapAdjust(H, i, H.length); for (i = H.length; i > 1; i--) { swap(H.r[1], H.r[i]); HeapAdjust(H, 1, i - 1); } }
归并排序 ()
基数排序 ()
稳定性: 选择排序、堆排序、快速排序是不稳定的, 其他是稳定的.
归并排序最坏情况下的比较次数:
1
2
3
4
5
6
7
8
9
10
0
1
3
5
9
11
14
17
25
27
快速选择算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 第 k 小 RcdType QuickSelect(SqList &L, int st, int en, int k) { if (st == en) return L.r[st]; low = st; high = en; pivotkey = L.r[st]; while (low <= high) { while (low <= high && L.r[low].key < pivotkey) low++; while (low <= high && L.r[high].key > pivotkey) high--; if (low <= high) swap(L.r[low++], L.r[high--]); } if (st + k - 1 <= high) return QuickSelect(L, st, high, k); if (st + k - 1 >= low) return QuickSelect(L, low, en, k - (low - st)); return L.r[high + 1]; }
对于一个热爱数学的人来说，思考是经常做的事。例如，11 月学到定积分的时候，我在网上搜到一本 Pete Clark 所著的 Honors Calculus，顺着作者的思路，理解了达布积分和黎曼积分的等价性的证明——而这一切源于我对“闭区间上的连续函数都是可积的”的断言的疑惑。例如，我现在有时候会回顾那些曾经学过的数学知识，例如三角形的面积等于底乘高的一半，然后发现它并不显然的（即使不定义面积，也至少要证明分别取三条边为底算出来的结果是一样的）。
许多问题，当我们司空见惯时，我们就不愿意思考了。我们放弃思考之日，就是邪恶宣告胜利之时。然而，一旦我们形成了思考的习惯，这就成为了一股强大的力量。就像哈佛大学教授 Micheal Sandel 在政治哲学课程“公正：该如何做是好？”（Justice: What’s the Right Thing to Do?）的最后一节课上说的那样：
I tried to warn you that once the familiar turns strange, once we begin to reflect on our circumstance, it’s never quite the same again. I hope you have, by now, experienced at least a little of this unease, because this is the tension that animates critical reflection, and political improvement, and maybe even the moral life as well. … Why do these arguments keep going, even if they raise questions that are impossible ever finally to resolve? The reason is that we live some answer to these questions all the time. The aim of this course has been to awaken the restlessness of reason, and to see where it might lead. … And if the restlessness continues to afflict you in the days and years to come, then we together have achieved no small thing.
2024 is the year that half of humanity goes to the polls—and all of humanity will be affected. I stand before you in this whirlwind convinced of two overriding truths. First, the state of our world is unsustainable. We can’t go on like this. And second, the challenges that we face are solvable. But that requires us to make sure the mechanisms of international problem-solving actually solve problems. ——联合国秘书长安东尼奥·古特雷斯向联合国大会的报告（2024 年 9 月 24 日）
2024 年必然是世界历史上可圈可点的一年——人类的一半前往投票站（Half of humanity went to the polls；我思前想后还是决定直译）。人们满怀期待地进入这史无前例的一年，带着对更好的明天的憧憬。
期中考后，微积分课开始讲积分。出于好奇，我阅读了 Pete Clark 所著Honors Calculus（这个 PDF 版本有许多笔误，似为草稿）的第八章第 1、2、4 节。为了理解部分内容，我还阅读了第六章第 4 节对实数归纳法的正确性的证明。以下为我的笔记，第 1、2、3 节分别对应原书第八章第 1、2、4 节。也可以作为该书这一部分的浓缩版。
第 1 节 微积分基本定理
我们希望 上全体可积函数（可求定积分的函数）组成的集合 满足以下性质： (I0) a) 上的所有连续函数属于 。 b) 上的函数都有界。
