a + b = O（n^2）的时间复杂度？

Question

我正在阅读“算法导论”，并被卡在第3章，作者说，“更令人惊讶的是，当> 0时，任何线性函数an + b为O（n^2）中的 ” Can有人解释如何证明这一点？

Answer 1

线性函数an + b是O(n^2)通过定义：对于足够大的n，an + b小于cn^2与常数，例如c = 1。

请注意，O(n^2)是一个上限，但不是一个紧的。一旦你可以证明一个更紧的界限（在这种情况下，上限），一个不太紧的界限就不是很有用。

Answer 2

对于直觉，“大O”符号的思想是从足够大的输入开始，成本函数的增长速度不会比O（...）快。就是这样，它只是一个上限。

线性函数不会长得比二次函数，三次函数，指数函数等，他们都成长要快，因此an + b是O(n^2)，也O(n^3)，O(2^n)，O(n!)等

但是，它的增长快于对数 - 所以你不能说它是O(log n)。