《算法导论（原书第3版）》一本章注记

本章注记

Knuth［209］追溯O记号的起源到1892年由P.Bachmann编写的一本数论教材。E.Landau在1909年发明o记号，用于讨论素数的分布。Knuth［213］提倡Ω和Θ记号，以纠正文献中流行的但技术上草率的对上界和下界都使用O记号的常规。许多人在Θ记号技术上更准确的地方继续使用O记号。关于渐近记号的历史与发展的深入讨论，可以参考Knuth［209,213］以及Brassard和Bratley［55］撰写的著作。

虽然各种定义在大多数公共的情况下是一致的，但是，不是所有的作者都用相同的方式来定义渐近记号。一些可选的定义包括不是渐近非负的函数，只要它们的绝对值是适当有界的。

等式(3.20)应归功于Robbins［297］。基本数学函数的其他性质可以在任何一本好的数学参考书中找到，例如，Abramowitz和Stegun［1］或Zwillinger［362］，也可以在微积分书中找到，例如Apostol［18］或Thomas等［334］。Knuth［209］以及Graham、Knuth和Patashnik［152］包含大量用于计算机科学中的离散数学的有关材料。