时间复杂度

Question

嗨，我有一个问题：

假设我有T(n) = m * n^2 (n<m)，这样写T(n) = O(m)正确吗？因为我写了T(n) = m*n*n所以因为n<m我们有T(n) = O(m)谢谢

Answer 1

不，你能做的最好的事情就是写T(n,m) = O(m^3)。n < m是一个非常弱的条件，基本上只会给你n in O(m)。例如，n可以始终为m-1。

编辑：我的第一个答案是不精确的，因为T只是n中的一个函数。如果m是常数，答案仍然成立，但O(m^3)等于O(1)。

Answer 2

我相信在这种情况下T(n) = O(n^2)

big-O的formal definition：

f(x) = O(g(x))当且仅当存在一个正实数M和一个实数x0使得对所有x> x0 |f(x)|≤M|g(x)|。

在您的情况下，T(n)将始终小于或等于m(n^2)。