时间复杂度

Question

你好 我有一个问题：

考虑我有 T(n) = m * n^2 (n T(n) = O(m) 这样写是否正确？因为我写了 T(n) = m*n*n 所以因为 n 我们有 T(n) = O(m) > 谢谢

Answer 1

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

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

Answer 2

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

正式定义大O的：

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

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