大O时间复杂度

Question

我有一个时间复杂度T（n）= 6n + xn，显然大O复杂度是（n^2），但我认为它会是（n）。我想了解它为什么是（n^2）。

Answer 1

T（N）= O（G（N））中的计算机科学指本

所以明显的T（n）的函数在集合O属于（N^2）

但主要问题是，你在T（n）中的'x'是否依赖于n的输入？

如果答案是肯定的，那么很明显，T（N）= O（N）+ XN属于集合为O（n^2）

如果答案是否定的，并且x是只是一个常数因子，以及那么T（n）当然属于也是 O（n^2）（松散的上限）。但是更紧的上界是T（n）属于O（n），因为T（n）= O（n）+ O（n）因为我们正在谈论上限大O符号），说O（n）函数也属于集合O（n^2）是正确的。如果我们只关心我们的算法甚至在最坏情况下在O（n^2）时间执行。

希望这会有所帮助