算法复杂度分析

AI协作题（1）- 前缀和非负的排序数

算法实现

使用卡特兰数公式：math.comb(2 * n, n) // (n + 1)

复杂度分析

时间复杂度：O(n)

• math.comb(2*n, n) 计算组合数 C(2n, n)
• Python 的 math.comb(n, k) 实现使用高效的迭代算法，时间复杂度为 O(k)
• 对于 math.comb(2*n, n)，k = n，因此时间复杂度为 O(n)
• 实现原理：避免计算大阶乘，而是通过循环 k 次直接计算：

  C(n, k) = n × (n-1) × ... × (n-k+1) / (k × (k-1) × ... × 1)
  

• 除法操作的时间复杂度为 O(1)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 只使用了常数个变量存储中间结果
• 空间复杂度：O(1)

---

AI协作题（2）- 最小化最大值之和

算法实现版本1：朴素DP（第89-213行）

时间复杂度：O(n²)

• 外层循环：遍历 i 从 1 到 n，共 n 次
• 内层循环：对于每个 i，从 i-1 倒序遍历到 0，最坏情况下需要遍历 i 次
• 内层循环中：
  • 累加操作：O(1)
  • 最大值更新：O(1)
  • DP 状态转移：O(1)
• 总时间复杂度：1 + 2 + … + n = n(n+1)/2 = O(n²)

空间复杂度：O(n)

• dp 数组：O(n)
• h 数组：O(n)
• 其他变量：O(1)
• 总空间复杂度：O(n)

算法实现版本2：单调栈+线段树优化（第223-376行）

时间复杂度：O(n log n)

• 外层循环：遍历 i 从 1 到 n，共 n 次
• 每次循环中的操作：
  1. 维护区间和限制（第339-343行）：
     • left 指针单调递增，每个元素最多被访问一次
     • 均摊时间复杂度：O(1)
  2. 单调栈维护（第347-360行）：
     • 每个元素最多入栈一次、出栈一次
     • 均摊时间复杂度：O(1)
     • 线段树区间更新：O(log n)
  3. 线段树单点更新（第365行）：
     • 时间复杂度：O(log n)
  4. 线段树区间查询（第369行）：
     • 时间复杂度：O(log n)
• 总时间复杂度：n × (O(1) + O(log n) + O(log n) + O(log n)) = O(n log n)

空间复杂度：O(n)

• 线段树：O(n)（4倍空间）
• dp 数组：O(n)
• h 数组：O(n)
• 单调栈：O(n)（最坏情况）
• 总空间复杂度：O(n)

---

改错题（1）- 最大路径权重问题

算法实现

暴力枚举每个点，对每个点重新运行DP

时间复杂度：O((N×M)²)

• 外层双重循环：枚举所有点 (r, c)，共 N×M 次
• 每次枚举中调用 get_max_path：
  • 初始化 DP 数组：O(N×M)
  • 填充 DP 数组：双重循环，O(N×M)
  • 返回结果：O(1)
• 总时间复杂度：(N×M) × O(N×M) = O((N×M)²)

空间复杂度：O(N×M)

• grid 数组：O(N×M)
• dp 数组（在 get_max_path 中）：O(N×M)
• 其他变量：O(1)
• 总空间复杂度：O(N×M)

---

改错题（2）- 合法的 h 序列

算法实现

动态规划，外层枚举 d，内层进行 DP 状态转移

时间复杂度：O(mn × n × max(a[i]))

• 外层循环 d：从 0 到 mn（mn 是 a[i] 的最小值），共 mn+1 次
• 内层循环 i：从 2 到 n，共 n-1 次
• 内层循环 j：从 1 到 a[i] - d，最多 a[i] 次
• 每次循环中的操作：
  • mmin 函数：O(1)
  • 数组访问和赋值：O(1)
  • 模运算：O(1)
• 总时间复杂度：
  • 最坏情况：mn = max(a[i])，此时为 O(max(a[i]) × n × max(a[i])) = O(n × max(a[i])²)
  • 一般情况：O(mn × n × max(a[i]))

空间复杂度：O(n × max(a[i]))

• g 数组：g[107][1007]，即 O(n × max(a[i]))
• a 数组：O(n)
• 其他变量：O(1)
• 总空间复杂度：O(n × max(a[i]))

---

总结

题目	算法	时间复杂度	空间复杂度
AI协作题（1）	卡特兰数公式	O(n)	O(1)
AI协作题（2）- 版本1	朴素DP	O(n²)	O(n)
AI协作题（2）- 版本2	单调栈+线段树	O(n log n)	O(n)
改错题（1）	暴力枚举+DP	O((N×M)²)	O(N×M)
改错题（2）	动态规划	O(n × max(a[i])²)	O(n × max(a[i]))