高级算法 (Fall 2026)

2026-09-09T04:42:41Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2026) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([[file:Hashing-26.pdf|slides]]) ([[Media:AA26-note-hashing-en.pdf|AI-generated lecture note]], [[Media:AA26-note-hashing-zh.pdf|AI生成讲义]])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2026)

2026-09-08T13:54:23Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2026) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([[Media:Hashing-26.pdf|slides]]) ([[Media:AA26-note-hashing-en.pdf|AI-generated lecture note]], [[Media:AA26-note-hashing-zh.pdf|AI生成讲义]])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

File:AA26-note-hashing-zh.pdf

2026-09-08T13:53:21Z

Etone:

File:AA26-note-hashing-en.pdf

2026-09-08T13:53:06Z

Etone:

高级算法 (Fall 2026)

2026-09-08T13:52:09Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2026) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([[Media:Hashing-26.pdf|slides]])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

File:Hashing-26.pdf

2026-09-08T13:47:20Z

Etone:

2026-04-08T08:38:47Z

Etone: Created page with "[http://en.wikipedia.org/wiki/Quicksort '''快速排序'''（'''Quicksort'''）]是由Tony Hoare发现的排序算法。该算法的伪代码描述如下（为方便起见，假设数组元素互不相同——更一般情况的分析易推广得到）： '''''QSort'''''(A): 输入A[1...n]是存有n个不同数字的数组 if n>1 then '''pivot''' = A[1]; 将A中<pivot的元素存于数组L，将A中>pivot的元素存于数组R; \\保持内部元素之..."

[http://en.wikipedia.org/wiki/Quicksort '''快速排序'''（'''Quicksort'''）]是由Tony Hoare发现的排序算法。该算法的伪代码描述如下（为方便起见，假设数组元素互不相同——更一般情况的分析易推广得到）：
'''''QSort'''''(A): 输入A[1...n]是存有n个不同数字的数组
if n>1 then
'''pivot''' = A[1];
将A中<pivot的元素存于数组L，将A中>pivot的元素存于数组R; \\保持内部元素之间相对顺序
递归调用'''''QSort'''''(L)和'''''QSort'''''(R);

该伪代码描述省略了对数组的存取归并等具体实现的交代。可以不妨认为算法中的<math>L</math>和<math>R</math>其实就分别是原数组<math>A</math>的前半部分<math>A[1...i-1]</math>和后半部分<math>A[i...n]</math>，其中<math>i</math>表示'''pivot'''（“'''基准'''”、“'''轴点'''”、“'''分水岭'''”元素）在数组<math>A</math>中的序数，即'''pivot'''是数组<math>A</math>中第<math>i</math>小的数。

作为基于比较的（comparison-based）排序算法，我们将算法进行的元素间的'''比较次数'''作为算法的复杂性度量。在'''最坏情况'''（'''worst-case'''）输入下，我们描述的“快速排序”算法所使用的比较次数可以达到<math>\Theta(n^2)</math>。而且有趣的是，这一<math>\Omega(n^2)</math>的复杂度下界是在输入数组是一个已排好序的数组时达到的：此时'''pivot'''会将数组<math>A</math>划分为大小极不平衡的子数组<math>L</math>和<math>R</math>，递归树也因此极不平衡，而算法使用的比较次数可因此达到<math>(n-1)+(n-2)+(n-3)+\cdots+1=\Omega(n^2)</math>。

现在我们来分析这一算法的'''平均情况'''（'''average-case'''）复杂度。
令输入数组<math>A</math>为<math>n</math>个元素的均匀分布的随机排列。如下性质不难递归验证：
{{Theorem|性质一（输入分布的递归不变性）|
* 作为基于比较的排序算法，快速排序算法的行为仅与输入数组<math>A</math>中元素的相对顺序有关，而与<math>A</math>中元素的具体数值无关。
* 进一步地，在算法的每次递归调用中，其输入数组中元素的相对顺序，符合该数量元素的所有排列上的均匀分布。
}}

= 快速排序算法的平均复杂度分析 I（基于全期望法则）=
令随机变量<math>X_n</math>表示在随机输入<math>A</math>下，快速排序算法使用的总比较次数。同时令<math>t(n)=\mathbb{E}[X_n]</math>表示其期望。正如刚刚解释的，<math>t(n)</math>是良定义的，因为期望值<math>\mathbb{E}[X_n]</math>仅与<math>n</math>有关。

对<math>1\le i\le n</math>，定义<math>B_i</math>为如下事件：
:*'''pivot'''在数组<math>A</math>中是第<math>i</math>小的元素。
则<math>B_1,B_2,\ldots,B_n</math>构成了对所有情况（样本空间）的一个划分。且每个事件<math>B_i</math>发生的概率有：
:<math>\Pr(B_i)=\frac{(n-1)!}{n!}=\frac{1}{n}</math>.
这是因为事件<math>B_i</math>等价于一个均匀分布的随机排列<math>\pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n]</math>有<math>\pi(1)=i</math>，而这件事的概率为<math>\frac{1}{n}</math>。

因此，根据'''全期望法则'''（'''law of total expectation'''），有：
:<math>
\begin{align}
t(n)
=
\mathbb{E}[X_n]
&=
\sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\Pr(B_i)
=
\frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i]
\end{align}
</math>.
而当事件<math>B_i</math>发生时，即当'''pivot'''恰为数组<math>A</math>中第<math>i</math>小的元素，
算法会将<math>A</math>中比'''pivot'''小的<math>(i-1)</math>个元素放入子数组<math>L</math>、将比'''pivot'''大的<math>(n-i)</math>个元素放入子数组<math>R</math>，这总共会花费<math>n-1</math>次比较。
而且，根据'''性质一'''中所述的输入分布的递归不变性，递归调用'''''QSort'''''<math>(L)</math>和'''''QSort'''''<math>(R)</math>各自所使用的总比较次数分别为<math>X_{i-1}</math>和<math>X_{n-i}</math>。
综上所述，有如下恒等关系：
:<math>
\mathbb{E}[X_n\mid B_i]
=
\mathbb{E}[n-1+X_{i-1}+X_{n-i}]
</math>.
因此，上述全期望因此可被计算如下：
:<math>
\begin{align}
t(n)
=
\mathbb{E}[X_n]
&=
\frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\\
&=
\frac{1}{n}\sum_{i=1}^n\mathbb{E}[n-1+X_{i-1}+X_{n-i}]\\
&=
n-1+\frac{2}{n}\sum_{i=0}^{n-1}\mathbb{E}[X_{i}] &\text{(根据期望的线性)}\\
&=
n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i).
\end{align}
</math>
我们因此建立了平均复杂度<math>t(n)=\mathbb{E}[X_n]</math>的如下递归式：
:<math>
\begin{align}
t(n)
&=
n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i)
&&
\text{if }n>1;\\
t(n)
&=
0
&&
\text{if }0\le n\le 1.
\end{align}
</math>
我们有若干种方法从这一递归式获得关于<math>t(n)=\mathbb{E}[X_n]</math>的真相：
* 一种是使用'''生成函数'''等工具来求解这样的递归方程，例如使用[[组合数学_(Fall_2025)/Generating_functions#Analysis_of_Quicksort|'''本学期组合数学课上的分析''']]，最终可精确解出<math>t(n)=2(n+1)H(n)-4n</math>，此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[https://en.wikipedia.org/wiki/Harmonic_number 调和数]；
* 另一种是采用'''数学归纳法'''来对我们猜想的关于<math>t(n)</math>的界进行验证，例如从<math>t(n)\le c n \ln n</math>的归纳假设出发，尝试使<math>c</math>尽量小。令该归纳假设对于所有<math>0\le i<n</math>都成立，则对于<math>t(n)</math>，根据递归式因此有：
:<math>
\begin{align}
t(n)
&=
n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i)\\
&\le
n-1+\frac{2c}{n}\sum_{i=1}^{n-1}i \ln i &&\text{(归纳假设)}\\
&\le
n-1+\frac{2c}{n}\int_{1}^nx \ln x\,\mathrm{d}x &&\text{(求和的积分上界)}\\
&=
n-1+\frac{c}{2n}\left(2n^2\ln n-n^2+1\right)\\
&=
cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n}
\end{align}
</math>
设<math>c=2</math>时，有<math>t(n)\le cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n}\le 2 n \ln n</math>对于所有<math>n\ge 1</math>总是成立。

= 快速排序算法的平均复杂度分析 II（基于期望的线性）=
令随机变量<math>X</math>表示在随机输入<math>A</math>下，快速排序算法使用的总比较次数。我们希望分析得到期望<math>\mathbb{E}[X]</math>的上界。

假设输入数组<math>A</math>中的元素，在从小到大排序之后为<math>a_1<a_2<\cdots a_n</math>。
对<math>1\le i<j\le n</math>，令布尔值随机变量<math>I_{ij}=I(A_{ij})\in\{0,1\}</math>指示如下事件的发生：
* <math>A_{ij}</math>：元素<math>a_i</math>和<math>a_j</math>在算法运行过程中被比较了。

容易验证：在算法运行过程中，任何元素对<math>a_i</math>和<math>a_j</math>之间至多只会进行一次比较。
因此总比较次数<math>X</math>可被计算如下：
:<math>X=\sum_{i<j}I_{ij}</math>.
根据'''期望的线性'''（'''linearity of expectation'''）：
:<math>\mathbb{E}[X]=\sum_{i<j}\mathbb{E}[I_{ij}]=\sum_{i<j}\Pr(A_{ij})</math>.

因此接下来，仅需要针对每一对具体的<math>1\le i<j\le n</math>，计算概率：
:<math>\Pr(A_{ij})=\Pr(a_i\text{和}a_j\text{在算法中进行了比较})</math>.
而事件<math>A_{ij}</math>发生，当且仅当：在'''某次'''递归调用中，<math>a_i</math>与<math>a_j</math>同属于当前输入数组，且'''pivot'''恰好选中<math>a_i</math>或<math>a_j</math>二者之一。
注意到：假如<math>a_i</math>与<math>a_j</math>同属于当前输入数组，则当前数组必然也同时包含它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>；
同时，事件<math>A_{ij}</math>的发生与否，仅当'''首次'''在某递归调用中'''pivot'''选中了<math>\{a_k\mid i\le k\le j\}</math>中的元素，才会确定。
综上，于是有：
:<math>\Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1}</math>.

{|border="1"
|如果你认为该证明不够详细。这里再提供一个对于上述事实的详细证明。

定下任意一对具体的<math>1\le i<j\le n</math>。
在算法运行之初（顶层递归调用），元素<math>a_i</math>与<math>a_j</math>显然有<math>a_i<a_j</math>，且同属于当前递归调用的输入数组<math>A</math>。

事件<math>A_{ij}</math>的发生与否，由如下的递归随机过程确定：
# 在当前输入元素中按均匀分布随机选择'''pivot'''元素。如果刚好选中<math>a_i</math>或<math>a_j</math>二者之一，那么<math>a_i</math>与<math>a_j</math>之间必被比较（因为'''pivot'''会与当前数组内的所有元素进行比较）。此情况下，事件<math>A_{ij}</math>确定发生。
# 如果<math>a_i<</math>'''pivot'''<math><a_j</math>，即'''pivot'''取值在<math>a_i</math>与<math>a_j</math>之间，此时<math>a_i</math>与<math>a_j</math>会被大小居于其中间的'''pivot'''元素分别分流到子数组<math>L</math>与<math>R</math>中，且在之后的递归调用中永不再见，因此不会被比较。此情况下，事件<math>A_{ij}</math>确定不发生。
# 如果'''pivot'''选中了比<math>a_i</math>更小或者比<math>a_j</math>更大的元素，在此情况下<math>a_i</math>与<math>a_j</math>，连同它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>，都会被分到同一个子数组<math>L</math>（假如'''pivot'''<math>>a_j</math>）或者<math>R</math>（假如'''pivot'''<math><a_i</math>）中。而此时<math>A_{ij}</math>的发生与否尚未能在这一层递归调用中确定，则需进入下一层递归调用，将当前输入数组改为<math>a_i</math>与<math>a_j</math>所同属的那个子数组（即<math>L</math>如果'''pivot'''<math>>a_j</math>，<math>R</math>如果'''pivot'''<math><a_i</math>），然后回到（1）重复。
不难看出该递归过程跟踪模拟了事件<math>A_{ij}</math>的发生与否，在快速排序算法的递归调用过程中，是如何被确定下来的。

因此，可以得出：<math>A_{ij}</math>发生，当且仅当在上述情况（1）或（2）之一发生的前提下有（1）发生。

除此之外，如下两个观察通过递归验证易得：
* 当<math>a_i</math>与<math>a_j</math>同属于当前递归调用的输入数组时，它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>也属于该数组；
* 在任何递归调用中，'''pivot'''始终在当前输入数组中均匀分布——这也可由'''性质一'''所述的输入分布的递归不变性得到。
综上可得：
:<math>\Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1}</math>.
|}

算法总比较次数的期望<math>\mathbb{E}[X]</math>可被计算如下：
:<math>\begin{align}
\mathbb{E}\left[X\right]
&=
\sum_{i<j}\Pr(A_{ij})\\
&=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\frac{2}{j-i+1}\\
&= \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\text{令 }k=j-i+1)\\
&\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\
&= 2n\sum_{k=1}^{n}\frac{1}{k}\\
&= 2n H(n).
\end{align}</math>
此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[http://en.wikipedia.org/wiki/Harmonic_number 调和数]。

如果更加仔细一些，我们甚至可以计算出总比较次数期望<math>\mathbb{E}[X]</math>的精确值：
:<math>\begin{align}
\mathbb{E}\left[X\right]
&=
\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k}\\
&=
\sum_{j=2}^n\sum_{k=2}^{j}\frac{2}{k} && \text{(令$j=n-i+1$)}\\
&=
\sum_{k=2}^{n}\frac{2(n-k+1)}{k} && \text{(交换求和顺序)}\\
&=
\sum_{k=2}^{n}\left(\frac{2(n+1)}{k}-2\right)\\
&=
2(n+1)\sum_{k=2}^{n}\frac{1}{k}-2(n-1)\\
&=
2(n+1)\sum_{k=1}^{n}\frac{1}{k}-4n\\
&=
2(n+1)H(n)-4n.
\end{align}</math>