首页/资讯中心/详情

算法设计与分析全题型答题模板大全

算法设计与分析全题型答题模板大全
📅 发布时间：2026/6/21 2:11:43

一、函数增长率排序（Asymptotic Growth Ordering）

适用场景：Problem Set 1 第1题。给一堆奇怪函数（如指数嵌套、阶乘），按增长率从小到大排。

答题模板（英文正文）：

  1. Simplify the expressions using logarithm/exponent rules (e.g., (\log_2 8^n = 3n), constants are (O(1))).
  2. Categorize into general complexity classes: Constant (\ll) Logarithmic (\ll) Polynomial (\ll) Exponential (\ll) Factorial.
  3. For exponentials ((a^n)), compare the base (a) and the growth rate of the exponent. For polynomials, compare the degree.
  4. Final order: Write the sequence using strict inequalities, e.g., (f_5 < f_3 < f_8 < \dots).

二、主定理与递推式求解（Master Theorem）

适用场景：Problem Set 1 归并排序复杂度推导，或分治算法（Karatsuba/Strassen）的复杂度分析。

答题模板（英文正文）：

  1. Identify the recurrence form: (T(n) = aT(n/b) + O(n^d)).
  2. Compare (\log_b a) with (d):
    • If (\log_b a > d), then (T(n) = O(n^{\log_b a})).
    • If (\log_b a = d), then (T(n) = O(n^d \log n)).
    • If (\log_b a < d), then (T(n) = O(n^d)).
  3. Conclusion: Substitute the specific constants to get the final complexity.

三、分治算法设计（Divide and Conquer）

适用场景：Problem Set 1 链表归并排序 / 网格找局部最小值；或高级题 Karatsuba乘法 / 最近点对。

答题模板（英文正文）：

  1. Divide: Split the input into (a) subproblems of size (n/b) (e.g., split the grid by middle row/column, or split numbers into two halves).
  2. Conquer: Recursively solve these subproblems.
  3. Combine: Merge the results with cost (O(n^d)) (e.g., linear merge, or boundary probing for grid local min).
  4. Recurrence: Write (T(n) = aT(n/b) + O(n^d)). Apply Master Theorem.
  5. Correctness (Induction): Assume recursive calls return correct results for subproblems. The merge step correctly combines them, so the overall algorithm is correct.

四、贪心算法（Greedy）与交换论证（Exchange Argument）

适用场景：Problem Set 1 区间覆盖 / 最小加油次数；或课程中的区间调度 / 最小生成树。

答题模板（英文正文）：

  1. Algorithm description: Sort the items (by finish time / coordinate / deadline). Initialize (R = -\infty) and (count = 0). Iterate, selecting the first compatible item and updating (R).
  2. Proof of Correctness (Exchange Argument):
    • Let (G) be the greedy solution and (O) be an optimal solution. Suppose they share the first (k-1) choices.
    • At step (k), greedy picks (g) (with the earliest finish time / farthest reach). Let (o) be the (k)-th choice in (O).
    • Since greedy picks optimally, (finish(g) \le finish(o)) (or (reach(g) \ge reach(o))).
    • Exchange: Replace (o) with (g) in (O). Feasibility is maintained and quality does not decrease. Repeating this transforms (O) into (G).
  3. Complexity: Sorting dominates, total (O(n \log n)).

五、动态规划（Dynamic Programming）

适用场景：Problem Set 2 最大和递增子序列 / 分组背包 / 区间涂色；或课程中序列比对 / Bellman-Ford。

答题模板（英文正文）：

  1. State Definition: Define (dp[i]) (or (dp[i][w]), or (f[i][j])) as the optimal value for the subproblem ending at (i) / using first (i) items / covering interval ([i, j]).
  2. Base Case:
    • LIS: (dp[i] = a[i]).
    • Group Knapsack: (dp[0][w] = 0).
    • Interval Painting: (f[i][i] = 1).
  3. Transition Equation:
    • LIS: (dp[i] = \max(a[i], \max_{j < i, a[j] < a[i]} (dp[j] + a[i]))).
    • Group Knapsack: (dp[i][w] = \max(dp[i-1][w], \max_{c \le w} (dp[i-1][w-c] + v))).
    • Interval Painting: If (s[i] = s[j]), then (f[i][j] = f[i][j-1]); else (f[i][j] = \min_{k} (f[i][k] + f[k+1][j])).
  4. Complexity: Time (O(n^2)) / (O(nW)) / (O(n^3)); Space accordingly.
  5. Correctness (Optimal Substructure): The recurrence considers all possible choices for the last element / partition point and takes the optimum over them, thus covering every feasible solution.

六、网络流建模（Max Flow / Min Cut）

适用场景：Problem Set 2 Ford-Fulkerson手算增广 / 学生选课建模 / Animal Crossing二分答案；或课程中图像分割 / 棒球淘汰。

答题模板（英文正文）：

  1. Ford-Fulkerson Execution (for hand calculation):
    • Find an augmenting path (s \to \dots \to t).
    • Compute bottleneck (f = \min)(residual capacities along the path).
    • Update: forward edges (-= f), backward edges (+= f).
    • Repeat until no (s)-(t) path exists in the residual network.
    • Max Flow Value= sum of bottlenecks. By Max-Flow Min-Cut Theorem, this equals min cut capacity.
  2. Flow Network Construction (for modeling):
    • Create super source (S) and sink (T).
    • Left side (Students/Days): (S \to Node), capacity = limit (e.g., (k_i), or daily capacity).
    • Middle (Eligibility): Left (\to) Right, capacity = 1 or (\infty), if the relation exists.
    • Right side (Courses/Events): Node (\to T), capacity = demand (e.g., (c_j)).
  3. Feasibility Check: Compute Max Flow. If it equals the total demand ((\sum c_i)), the instance is feasible.

七、NP-完全性证明（NP-Completeness Proof）—— 必考大题！

适用场景：Problem Set 3 链路干扰 / 巡逻点 / 单调3-SAT / 双容量装箱 / 网格黑白棋子。

答题模板（英文正文）：

  1. Show the problem is in NP: Given a certificate (e.g., subset (L’)), we can verify (|L’| \ge k) and scan all constraints in (O(|V|+|E|)) time. Thus it is in NP.
  2. Polynomial-time Reduction from a known NPC problem:
    • State: “We reduce fromIndependent Set / Vertex Cover / 3-SAT / Subset Sum.”
    • Mapping: Construct the instance explicitly (e.g., “For each vertex (v_i), create a link (\ell_i). For each edge ((u,v)), create an interference pair ((\ell_u, \ell_v)).”). This takes polynomial time.
  3. Correctness (Bidirectional):
    • ((\Rightarrow)): If the known problem instance is YES (e.g., there is an independent set of size (k)), then the constructed instance is also YES (the corresponding links have no conflicts).
    • ((\Leftarrow)): If the constructed instance is YES (e.g., a set of non-conflicting links), then mapping back yields a YES solution to the known problem (a valid independent set).
  4. Conclusion: Since the problem is in NP and an NPC problem reduces to it, the problem is NP-Complete.

八、PSPACE 与 QSAT（概念/简答）

适用场景：Problem Set 3 没直接考，但课程讲义有。如果问“PSPACE-complete是什么”或“QSAT怎么理解”。

答题模板（英文正文）：

  1. Definition of QSAT: A quantified Boolean formula (\exists x_1 \forall x_2 \exists x_3 \dots \Phi(x_1, \dots, x_n)), where (\Phi) is a 3-CNF.
  2. Interpretation: This models a two-player game. The (\exists) player chooses values for existential variables, and the (\forall) player chooses for universal variables. The question is whether the (\exists) player has a winning strategy.
  3. PSPACE-Completeness: QSAT is the canonical PSPACE-Complete problem. It is considered harder than NP because it involves alternating quantifiers (game-playing), whereas NP only involves a single (\exists) quantifier.

九、参数化算法（FPT - Fixed Parameter Tractability）

适用场景：课程讲义重点。问“小顶点覆盖（Vertex Cover）当k很小时怎么设计算法”。

答题模板（英文正文）：

  1. Algorithm (Branching):
    • If (G) has no edges, return True.
    • If (k < 0), return False.
    • Pick an arbitrary edge ((u, v)).
    • Branch 1: include (u) in the cover, recurse on (G - {u}) with (k-1).
    • Branch 2: include (v) in the cover, recurse on (G - {v}) with (k-1).
  2. Time Complexity: (T(n, k) = 2T(n-1, k-1) + O(n) \implies O(2^k \cdot n)).
  3. Correctness: For any edge, at least one endpoint must be in the vertex cover. Both possibilities are considered, so no solution is missed.

十、局部搜索与纳什均衡（Local Search / Nash Equilibrium）

适用场景：课程讲义高级题。问“最大割局部最优的近似比”或“路由博弈的势函数”。

答题模板（英文正文）：

  1. Local Search for Max-Cut: Start with any partition. Repeatedly flip a vertex if moving it to the other side increases the cut. Stop at a local optimum.
  2. Approximation Guarantee: Any local optimum for Max-Cut is a2-approximation(cut size (\ge OPT/2)).
  3. Potential for Routing:
    • Define (\Phi = \sum_{e} c_e \cdot H(x_e)), where (x_e) is load on edge (e).
    • When a player changes route to lower their own cost, (\Phi) strictly decreases. Since (\Phi) is bounded below, a Nash Equilibrium exists.
    • Price of Stability (PoS): Best Nash equilibrium is at most (H(k) = O(\log k)) times the social optimum.

十一、摊还分析（Amortized Analysis）

适用场景：Problem Set 4 懒队列 / 墓碑压缩 / 三角数校准；或课程中斐波那契堆 / 动态表。

答题模板（英文正文）：

  • Aggregate Method: Sum total cost over (m) operations. Since each element (queue entry / tombstone) is processed at most once, total cost is (O(m)). Amortized cost (= O(1)).
  • Accounting Method: Charge each operation (c) tokens. Actual cost is (a). Store (c-a) credits. Prove the credit balance is never negative (e.g., each insertion stores 1 credit, which pays for future expensive deletions).
  • Potential Method: Define (\Phi) (e.g., (\Phi = C \cdot |Q|), or (\Phi = C \cdot #\text{Tombstones})). Ensure (\Phi_0 = 0) and (\Phi_i \ge 0). Compute (\hat{c}i = c_i + \Phi_i - \Phi{i-1}). Show (\hat{c}_i = O(1)). The potential drop pays for the expensive operations.

十二、概率与随机算法（Probability & Randomized）

适用场景：Problem Set 4 超几何抽样 / 随机优先级选点；或课程中 MAX-3SAT / Karger最小割 / 布隆过滤器。

答题模板（英文正文）：

  1. Define Indicator Variables: Let (X_i = 1) if event (i) occurs (e.g., bad submission is selected, or clause is satisfied), else 0.
  2. Single-event Probability:
    • Sampling: (\Pr[X_i = 1] = s/n).
    • Random Priority (Graph): (\Pr[v \in S] = 1/(\deg(v)+1)).
    • MAX-3SAT: A random assignment satisfies a clause with probability (1 - (1/2)^3 = 7/8).
  3. Expectation via Linearity(No independence needed!):
    • (\mathbb{E}[X] = \sum \mathbb{E}[X_i]). Simplify (e.g., for regular graph, (E[|S|] = n/(d+1)); for 3SAT, (E[#satisfied] = 7m/8)).
  4. Tail Bound / Sufficient Condition:
    • Failure probability: (\Pr[\text{No violation}] \le (1 - r/n)^s \le e^{-rs/n}).
    • Set (e^{-rs/n} \le \delta \implies s \ge \frac{n}{r} \ln(1/\delta)).
  5. Bloom Filter Property: No False Negatives (if it says “not in set”, definitely not). May have False Positives with probability ((1 - e{-kn/m})k).

十三、近似算法（Approximation Algorithms）

适用场景：课程讲义 Lecture 24。问“List Scheduling的近似比”或“Set Cover的贪心近似”。

答题模板（英文正文）：

  1. List Scheduling (2-approximation):

    • Algorithm: Assign each job to the currently least loaded machine.
    • Let (M) be the makespan. Let job (j) be the last job to finish, with length (t), and start time (T).
    • Before job (j), all machines were busy, so (T \le OPT). Also, (t \le OPT).
    • Therefore, (M = T + t \le 2OPT). It is a 2-approximation.

  2. Greedy Set Cover ((H(n))-approximation):

    • Algorithm: Repeatedly pick the set that covers the most uncovered elements.
    • The approximation ratio is (\ln n) (where (n) is the number of elements).
    • Proof by charging: Each element is charged at most (OPT / (\text{remaining uncovered elements})), summing to (OPT \cdot H_n).

考场战术提醒：拿到卷子先看题目属于上述哪一个编号，然后把对应英文模板的开头几句话（如“We reduce from…”、“Define (dp[i]) as…”、“By Master Theorem…”）先写上，保证基础框架分到手。计算题把数字套进公式，概念题把黑体关键词写全。你已经武装到牙齿了，加油！ 🚀