大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)受限于f(n)。记作g(n)=O(f(n))。 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
渐进分析法最常用的表示方法是用于描述函数渐近行为的数学符号，更确切地说，它是用另一个（通常更简单的）函数来描述一个函数
数量级的渐近上界。
大O符号是由德国
数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《
解析数论》（
Analytische Zahlentheorie）首先引入的。
我们常用大O表示法表示
时间复杂度，注意它是某一个算法的时间复杂度。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2），它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外，一个问题本身也有它的
复杂度，如果某个算法的复杂度到达了这个问题复杂度的下界，那就称这样的算法是最佳算法。
5-28
原文：https://www.cnblogs.com/coder-2017/p/9101756.html
