algorithm - 算法 A 的运行时间至少为 O(n²) - 为什么它毫无意义？

Question

为什么是这样的说法:

The running time of algorithm A is at least O(n²)

没有意义？

The running time of Insertion sort algorithm is at most O(n²)

是否正确？

我尝试了网络，但无法得到很好的解释。

我还有一个问题:

I know that any linear function a⋅n+b is O(n) and also O(n²). Is it also O(n³)?

Answer 1

T(n):Algo A的运行时间。我们只关心T(n)的上限和下限语句:T(n) >= O(n^2)

上界:因为 T(n) >= O(n^2)，所以没有关于 T(n) 上界的信息下界:假设 f(n) = O(n^2)，则语句:T(n) >= f(n)，但 f (n) 可以是任何比 n^2 更“小”的东西，例如:constant, n,...，所以没有关于更小的结论T(n) 的界限也是

=> 声明无意义