如题,昨天在刷 USACO GUIDU 时看到了时间复杂度的专题,在这个专题中有这样一段代码。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
for (int i = 1; i <= m; i++) {
}
文章中提到这段代码是 O(n2+m) 的,但给的原因是:
The following code is
O(n2+m)
, because it consists of two blocks
of complexity
O(n2)
and
O(m)
, and neither of them is a
lower order function with respect to the other.
我个人对这段话的理解是因为两个模块都不是相对于另一个的低阶函数。但 n2 的次数是 2, m 的次数是 1,难道不是 n2 的次数比 m 的次数要大吗?
请大佬解惑为什么这段代码是 O(n2+m) 的,而不是 O(n2) 的,谢谢。