算法作业1

第一部分：概念题

1. 渐进复杂度（大O）递增顺序排列

思路： 比较两个函数增长率最有效的方法是取对数，或者看当 $n \to \infty$ 时它们属于哪种量级（常数、对数、多项式、次指数、指数）。

• a. 组1：
  • $f_1(n) = n^{0.999999} \log_2 n$：接近线性，但因为多项式 $n^\epsilon$ 永远增长得比 $\log n$ 快，所以当 $n$ 极大时，它比 $n^1$ 增长慢。
  • $f_2(n) = 999999n = O(n)$：标准的线性复杂度。
  • $f_3(n) = 1.000002^n$：指数级复杂度（底数大于1）。
  • $f_4(n) = n^2 + 5n = O(n^2)$：二次多项式复杂度。
  • 结论： $f_1 < f_2 < f_4 < f_3$
• b. 组2：
  • $f_1(n) = 2^{2^{200000}}$：这是一个极大的常数，其中不含 $n$，所以复杂度是 $O(1)$。
  • $f_2(n) = 2^{200000n} = (2^{200000})^n$：极大的指数级复杂度。
  • $f_3(n) = \binom{n}{3} = \frac{n(n-1)(n-2)}{6} = O(n^3)$：三次多项式。
  • $f_4(n) = n \cdot n^{1/3} = n^{4/3} \approx n^{1.33}$：多项式复杂度。
  • 结论： 常数 < 低阶多项式 < 高阶多项式 < 指数。即 $f_1 < f_4 < f_3 < f_2$
• c. 组3：
  • $f_1(n) = n^{2\sqrt{n}}$：两边取对数为 $2\sqrt{n}\log_2 n$。属于次指数级（比多项式大，比指数小）。
  • $f_2(n) = 3^n$：指数级。取对数为 $n \log_2 3 \approx 1.58n$。
  • $f_3(n) = n^{15} \cdot 2^{n/3}$：指数级。取对数为 $\frac{n}{3} + 15\log_2 n \approx 0.33n$。
  • $f_4(n) = \sum_{i=1}^n (2i+3) = 2\frac{n(n+1)}{2} + 3n = n^2 + 4n = O(n^2)$：多项式。
  • 结论： 多项式 < 次指数 < 小底数指数 < 大底数指数。即 $f_4 < f_1 < f_3 < f_2$

---

2. 递推关系运行时间求解

思路： 针对多变量的递归式，我们可以利用递归树展开法（展开迭代）来求和计算。

• a. $T(x,y) = \Theta(x+y) + T(x/3, y/3)$
  • 解题过程： 将递归式不断向下展开： $T(x,y) = (x+y) + (\frac{x}{3} + \frac{y}{3}) + (\frac{x}{9} + \frac{y}{9}) + \dots + \text{BaseCase}$
  • 这是一个公比为 $1/3$ 的等比数列求和： $Sum \le (x+y) \sum_{i=0}^{\infty} (\frac{1}{3})^i = (x+y) \frac{1}{1 - 1/3} = \frac{3}{2}(x+y)$
  • 结论： 渐进复杂度为 $\Theta(x+y)$。
• b. $T(x,y) = \Theta(y) + T(x, y/4)$
  • 解题过程： 注意这里 $x$ 在递归时不减小，只有 $y$ 在减小。展开递归树： $T(x,y) = y + \frac{y}{4} + \frac{y}{16} + \dots + T(x, c)$
  • 其中 $y$ 相关的项是一个公比为 $1/4$ 的等比数列，其和为 $\Theta(y)$。
  • 当 $y$ 递归大约 $\log_4 y$ 次后到达边界值 $c \le 2$，此时触发边界条件 $T(x, c) = \Theta(x)$。
  • 将两部分相加：总代价 = 递归过程中的代价和 + 边界代价 = $\Theta(y) + \Theta(x)$。
  • 结论： 渐进复杂度为 $\Theta(x+y)$。
• c. 嵌套/互递归：$T(x,y) = \Theta(y) + S(x, y/2)$ ; $S(x,y) = \Theta(x) + 2T(x/2, y)$
  • 解题过程： 将 $S$ 的表达式代入 $T$ 中，得到单一函数的递归式。 $T(x,y) = \Theta(y) + \left[ \Theta(x) + 2T(x/2, y/2) \right] = \Theta(x+y) + 2T(x/2, y/2)$
  • 分析递归树： 第 0 层代价：$x+y$ 第 1 层：产生 2 个子问题，每个规模代价为 $\frac{x}{2}+\frac{y}{2}$，该层总代价 $2 \cdot (\frac{x+y}{2}) = x+y$ 第 2 层：产生 4 个子问题，每个规模代价为 $\frac{x}{4}+\frac{y}{4}$，该层总代价 $4 \cdot (\frac{x+y}{4}) = x+y$
  • 发现每一层的代价和均为 $\Theta(x+y)$。
  • 总共有多少层？取决于 $x$ 或 $y$ 哪个先达到边界。递归深度为 $k = \min(\log_2 x, \log_2 y)$。
  • 结论： 总时间为层数 $\times$ 每层代价，渐进复杂度为 $\Theta\Big((x+y) \min(\log x, \log y)\Big)$。

---

第二部分：编程题

1. 龙格-库塔公式求解微分方程

• a. 时空复杂度分析
  • 时间复杂度： 给定输入包含 $N$ 个步长节点。算法在每个节点处需要计算 $k_1, k_2, k_3, k_4$，这属于常数次运算 $O(1)$。一共需要迭代 $N$ 次，因此时间复杂度为 $O(N)$。
  • 空间复杂度： 如果仅仅为了求最后的一个终点值 $y_N$，我们只需要使用几个变量滚动存储当前步的 $y_n$ 即可，空间为 $O(1)$。但题目中经常需要输出所有节点的解以计算误差，若要保存所有步的 $y_n$ 序列，空间复杂度为 $O(N)$。（建议写 $O(N)$ 并在文档中说明是为了存储整个序列）。
• b. 编程实现与MSE计算
  • 题目方程：$y’ = \cos(x)$，初值 $y(0)=0$。理论真解 $y = \sin(x)$。
  • Python 代码实现：

import numpy as np

def f(x, y):
    # 微分方程的右侧式子 y' = f(x, y) = cos(x)
    return np.cos(x)

def exact_solution(x):
    # 真解 y = sin(x)
    return np.sin(x)

def runge_kutta_4(x0, y0, h, x_end):
    # 构建 x 的序列
    x_nodes = np.arange(x0, x_end + 1e-9, h) # 加上 1e-9 防止浮点数精度丢失导致漏掉最后一个点
    N = len(x_nodes)
    y_nodes = np.zeros(N)
    y_nodes[0] = y0
    
    # 四阶四段龙格库塔迭代
    for i in range(N - 1):
        x_n = x_nodes[i]
        y_n = y_nodes[i]
        
        k1 = h * f(x_n, y_n)
        k2 = h * f(x_n + h/2, y_n + k1/2)
        k3 = h * f(x_n + h/2, y_n + k2/2)
        k4 = h * f(x_n + h, y_n + k3)
        
        y_nodes[i+1] = y_n + (1/6) * (k1 + 2*k2 + 2*k3 + k4)
        
    return x_nodes, y_nodes

# 参数设定
x0 = 0.0
y0 = 0.0
h = 0.1
x_end = 2 * np.pi

# 进行数值求解
x_nodes, y_num = runge_kutta_4(x0, y0, h, x_end)
y_true = exact_solution(x_nodes)

# 计算 MSE (均方误差)
mse = np.mean((y_num - y_true)**2)

print(f"Nodes count (N+1): {len(x_nodes)}")
print(f"Mean Squared Error (MSE): {mse}")

# 选做：可以打印前几个点展示结果
print("\n部分节点的数值解与真解对比:")
print("x\t\tRK4解\t\t真解")
for i in range(5):
    print(f"{x_nodes[i]:.2f}\t\t{y_num[i]:.6f}\t{y_true[i]:.6f}")

提示：将上面这段代码在本地运行，把终端输出截图作为“通过截图”贴在文档里即可。由于RK4精度极高，得出的MSE应该在 $10^{-7}$ 到 $10^{-10}$ 这个非常小的数量级。

---

2. 水池高度算法设计

问题剖析： 有 $n$ 个底面积为1的坑，坑底高度为 $\alpha_i$。倒入体积为 $M$ 的水，水会填满最深的坑，求最终统一的水平面高度 $H$。 这是一个非常经典的“贪心/阈值”物理模拟题。若水面高度为 $H$，则只有底面 $\alpha_i < H$ 的坑才有水，水量守恒公式为： $M = \sum_{\alpha_i < H} (H - \alpha_i)$

1. 最优算法设计与思路：

• 方法一（作业通常期望的标准解法，$O(N \log N)$）： 将所有坑的高度 $\alpha$ 从小到大排序。我们假设最终水面漫过了前 $k$ 个深坑。 如果水漫过前 $k$ 个坑，则 $M = k \cdot H - \sum_{i=1}^k \alpha_i$。 可以反解出此时的水面高度估计值：$H_k = \frac{M + \sum_{i=1}^k \alpha_i}{k}$。 条件判断： 这个假设成立的条件是，计算出的水面 $H_k$ 必须正好漫过第 $k$ 个坑，且无法漫过第 $k+1$ 个坑。即需要满足数学条件验证： $\alpha_k < H_k \le \alpha_{k+1}$。 由于排序后从小到大遍历找 $k$，一旦满足该条件，即可停止。算法瓶颈在排序，时间复杂度 $O(N \log N)$。

• 证明算法是最优的（可选/加分项证明 $O(N)$）： 要解答“你能数学证明你的算法是最优的吗”，需指出：任何算法必须至少读取遍历一遍所有的 $\alpha_i$，以防止漏掉极深或极浅的坑，因此下界是 $\Omega(N)$。如果使用基于快排思想的随机选择算法（QuickSelect / Median of Medians）来代替全排序寻找分界点 $k$，我们可以在期望时间复杂度 $O(N)$ 内找到解，从而达到理论最优。（文档中你可以先写 $O(n\log n)$ 的解法，再提一句可以通过类似快速选择的减治法优化到 $O(N)$ 从而达到理论下界）。

2. 题目给定测试用例验算：

• $\alpha = {0.2, 0.5, 0.1, 0.8, 1.5, 0.4, 0.9}$, $M = 2$
• 排序后 $\alpha = {0.1, 0.2, 0.4, 0.5, 0.8, 0.9, 1.5}$
• $k=1$: $\alpha_1=0.1$。 $H_1 = (2 + 0.1)/1 = 2.1 > \alpha_2(0.2)$ (不满足条件，水会溢出到下一个坑)
• $k=2$: $\alpha_1+\alpha_2=0.3$。 $H_2 = (2 + 0.3)/2 = 1.15 > \alpha_3(0.4)$
• $k=3$: $\Sigma = 0.7$。 $H_3 = (2 + 0.7)/3 = 0.9 > \alpha_4(0.5)$
• $k=4$: $\Sigma = 1.2$。 $H_4 = (2 + 1.2)/4 = 3.2 / 4 = 0.8$。
• 检查条件：$\alpha_4 (0.5) < 0.8 \le \alpha_5 (0.8)$，完全符合！
• 计算结果：最终水面高度为 0.8。

3. 自拟测试用例与验证：

• 自举用例： $\alpha = {1, 2, 3}$, $M = 3$
• 验证过程： 排序后 ${1, 2, 3}$。 $k=1: H_1 = (3+1)/1 = 4 > 2$。 $k=2: H_2 = (3 + 1+2)/2 = 6/2 = 3$。验证 $\alpha_2(2) < 3 \le \alpha_3(3)$。满足。 故水面高度为 3。水坑1深度(3-1)=2，水坑2深度(3-2)=1，总水量=2+1=3，验证成功！

4. 编程实现代码 (Python)：

def find_water_level(alpha_list, M):
    # 按照从小到大排序
    sorted_alpha = sorted(alpha_list)
    n = len(sorted_alpha)
    
    # 提前加一个极大值作为虚拟的最高坑，为了让全部被水淹没时的边界判断不出界
    sorted_alpha.append(float('inf')) 
    
    current_sum = 0
    for k in range(1, n + 1):
        current_sum += sorted_alpha[k - 1]
        
        # 计算假设淹没前k个坑时的水位高度
        H_k = (M + current_sum) / k
        
        # 验证条件：H_k 是否严格漫过前k个，且没有漫过第k+1个
        if sorted_alpha[k - 1] < H_k <= sorted_alpha[k]:
            return H_k
            
    return -1 # 理论上不会走到这里，必定有解

# --- 测试用例 1 (题目指定) ---
alpha_test1 =[0.2, 0.5, 0.1, 0.8, 1.5, 0.4, 0.9]
M_test1 = 2
result_1 = find_water_level(alpha_test1, M_test1)
print(f"作业指定测试用例：\n坑底: {alpha_test1}, 水量: {M_test1}")
print(f"最终水面高度: {result_1:.4f}\n")

# --- 测试用例 2 (自举测试) ---
alpha_test2 = [1, 2, 3]
M_test2 = 3
result_2 = find_water_level(alpha_test2, M_test2)
print(f"自定义测试用例：\n坑底: {alpha_test2}, 水量: {M_test2}")
print(f"最终水面高度: {result_2:.4f}")

写文档建议： 在解答编程题文档时，一定要包含：1. 数学思想（公式推导）； 2. 核心代码（上面贴的）；3. 测试用例的运行截图（务必按照要求自己截个图）；4. 复杂度分析的说明。

祝你作业顺利拿高分！如果有哪里还需要深究的请随时告诉我。