问一个算法的时间复杂度问题，高分！！！

Question

一个算法的时间复杂度主要有两部分组成
o(n),和k(mn/k^2),那么这个算法的整体的时间复杂度应该如何写呢？
是写成o(n)+k(mn/k^2)吗？另外问一下：k(mn/k^2)和(mn)哪一个时间复杂度大？

Answer 1

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。.

Answer 2

复杂度是不管系数的。
m是什么？是常数还是和n相关的变量？下面按照常数处理。
ko(mn/k^2) = ko(m/k^2 * n) = ko(n) = o(n)
o(n)+k(mn/k^2) = o(n) + o(n) = o(n)

Answer 3

只要不是n的函数上式都成立，如果是n的函数，如：m = f(n)，代入mn/k^2中取得n的最大项就可以了。例如，如果m = n(n-1)，ko(mn/k^2) = o(mn/k^2) = o(n(n-1)n/k^2) = o(n^3)。