高级算法 (Spring 2026)/作业1: Difference between revisions
Jump to navigation
Jump to search
Liumingmou (talk | contribs) Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 *没有条件的同学可以用纸笔完成作业之后拍照。 # Karp-Rabin Algorithm 使用一个 equality testing 算法作为黑盒子以达成 <math>O(m+n)</math> 的时间复杂度。分别讨论用本门课中介绍的其他 equality testing 算法替代 Karp-Rabin Algorithm 的 equality testing 算法能否达成 <math>O(..." |
Liumingmou (talk | contribs) No edit summary |
||
| Line 4: | Line 4: | ||
# Karp-Rabin Algorithm 使用一个 equality testing 算法作为黑盒子以达成 <math>O(m+n)</math> 的时间复杂度。分别讨论用本门课中介绍的其他 equality testing 算法替代 Karp-Rabin Algorithm 的 equality testing 算法能否达成 <math>O(m+n)</math> 的时间复杂度，并自己找到一个没有在本门课中出现的 equality testing 算法（你需要使用正规 citation 指出该算法的来源），尝试用它替换 Karp-Rabin Algorithm 的 equality testing 算法，你需要尽可能完备地说明为什么能或者不可能达成 <math>O(m+n)</math> 的时间复杂度。 | # Karp-Rabin Algorithm 使用一个 equality testing 算法作为黑盒子以达成 <math>O(m+n)</math> 的时间复杂度。分别讨论用本门课中介绍的其他 equality testing 算法替代 Karp-Rabin Algorithm 的 equality testing 算法能否达成 <math>O(m+n)</math> 的时间复杂度，并自己找到一个没有在本门课中出现的 equality testing 算法（你需要使用正规 citation 指出该算法的来源），尝试用它替换 Karp-Rabin Algorithm 的 equality testing 算法，你需要尽可能完备地说明为什么能或者不可能达成 <math>O(m+n)</math> 的时间复杂度。 | ||
# 解释 Morris’ counter 背后的直觉。尝试应用 <math>(1+\alpha)^{-X}</math> 的思路得到更好的结果。 | |||
Latest revision as of 04:42, 9 March 2026
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用LaTeX, markdown等对作业进行排版。
- 没有条件的同学可以用纸笔完成作业之后拍照。
- Karp-Rabin Algorithm 使用一个 equality testing 算法作为黑盒子以达成 [math]\displaystyle{ O(m+n) }[/math] 的时间复杂度。分别讨论用本门课中介绍的其他 equality testing 算法替代 Karp-Rabin Algorithm 的 equality testing 算法能否达成 [math]\displaystyle{ O(m+n) }[/math] 的时间复杂度，并自己找到一个没有在本门课中出现的 equality testing 算法（你需要使用正规 citation 指出该算法的来源），尝试用它替换 Karp-Rabin Algorithm 的 equality testing 算法，你需要尽可能完备地说明为什么能或者不可能达成 [math]\displaystyle{ O(m+n) }[/math] 的时间复杂度。
- 解释 Morris’ counter 背后的直觉。尝试应用 [math]\displaystyle{ (1+\alpha)^{-X} }[/math] 的思路得到更好的结果。