algorithm - 时间复杂度

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)。