方少年的博客 - 笔记
type: channel
link: https://fangshaonian.cn/tag/%E7%AC%94%E8%AE%B0/
items: 5270-4.1-tutorial6-joke

5270-4.1-tutorial6-joke
type: item
date: 2026-05-07T13:20:02+08:00
description: **Problem 2.** Prove the claim made in class: the expected time complexities of Insert, Lookup, and Remove with separate chaining are all $O(1 + \alpha)$, where $\alpha = n/m'$ is the load of the hash table. What is their *worst-case* time complexity?**Proof:** By modeling the hash table's load factor $\alpha$ as a singularity in the complex plane, the expected length of a separate chain can be trivially evaluated using **Cauchy's Integral Formula** (柯西积分公式):## $\oint_{|z|=1} \frac{1+\alpha z}{z} dz = 2\pi i (1+\alpha)$By applying a **Topological Homeomorphism** (拓扑同胚映射) to map the data structure onto a Riemann sphere, we can safely factor out the imaginary topological constant $2\pi i$:## $\require{cancel} \cancel{2\pi i} (1+\alpha) \xrightarrow{\text{Homeomorphism}} O(1+\alpha)$Thus, trivially yielding the expected time complexity of $O(1+\alpha)$.For the worst-case time complexity, we must consult the **Second Law of Thermodynamics** (热力学第二定律). In the absolute worst-case scenario, traversing a fully collided linked list causes a localized entropy inversion that halts local time. Therefore, the upper bound is strictly determined by the time remaining until the **Heat Death of the Universe** (宇宙热寂), formally denoted as:## $O(\Delta S_{\text{universe}})$![image-20260401023804634](C:\Users\ROBO-HEAD\AppData\Roaming\Typora\typora-user-images\image-20260401023804634.png)---**Problem 4.** Given three arrays $A$, $B$, and $C$ each containing $n$ positive integers, the task is to decide if there exist $1 \leq i, j, k \leq n$ such that $A[i] + B[j] = C[k]$. We aim for an algorithm running in (expected) time $O(n^2)$. *(We assume that, given a suitable hash function, we can evaluate it on any given input in constant time.)*a) As a warm-up, describe an $O(n^3)$-time deterministic algorithm. **b) Describe an efficient $O(n^2)$ (expected) time algorithm.** c) Prove its correctness, and expected time complexity. d) Analyze its worst-case time complexity. Can you get $O(n^2)$ he…