《计算复杂性：现代方法》——0.3　大O记号

0.3　大O记号

算法的计算效率一般通过将该算法执行的基本操作的个数表达为算法输入的长度的函数来表示。这就是说，算法的效率用从自然数集N到其自身的函数T来刻画，T(n)是算法在所有长度为n的输入上执行的基本操作的最大个数。然而，函数T的形式有时严重地依赖于基本操作的具体定义。例如，在整数的加法中，基本操作既可以按照十进制（以10为基数）也可以按照二进制（以2为基数）来定义，但后者执行的基本操作个数是前者执行的基本操作个数的3倍还多。为了避免在基本操作的定义上纠缠不清而仅关注算法的宏观行为，采用下面的记号十分有益。