求解同余方程组的迭代构造方法的时间复杂度是多少？

适用条件

• 模数两两互质。
• 使用朴素迭代来查找每一步的乘数。

理解与推导

1. 识别同余方程的数量 k 及其模数 $m_1$, $m_2$, ..., $m_k$。
2. 认识到求解第一个同余方程需要 $O(1)$ 时间。
3. 对于每个后续同余方程 i（从 2 到 k），搜索最多需要 $m_i$ 步。
4. 将所有阶段的最大步数相加，得到总复杂度 O(sum_{$i=2$}^$k m_i$)。

例子

视频在黑板上明确写出“$O(m_2 + m_3 + m_4)$”并陈述：“从编程角度来看，这定义了算法的效率。时间复杂度由模数之和决定……因为每个阶段最多需要 $m_i$ 次迭代。”

容易误解的地方

• 假设复杂度是 O($m_1 * m_2$ * ... * $m_k$)。
• 忘记在这种特定的迭代表述中，第一个模数以不同于后续模数的方式对求和有贡献。

观看对应讲解

继续追问

• 为什么每个阶段的搜索受限于模数？
• 余数技巧如何改善实际计算？
• 如果模数不互质，复杂度会发生什么变化？