关于简单时间复杂度
  • 板块学术版
  • 楼主VectorLi
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/1/28 11:09
  • 上次更新2023/10/28 10:40:01
查看原帖
关于简单时间复杂度
609972
VectorLi楼主2022/1/28 11:09

如题,昨天在刷 USACO GUIDU 时看到了时间复杂度的专题,在这个专题中有这样一段代码。

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		// constant time code here
	}
}
for (int i = 1; i <= m; i++) {
	// more constant time code here
}

文章中提到这段代码是 O(n2+m)\mathcal{O}(n^2 + m) 的,但给的原因是:
The following code is O(n2+m)\mathcal{O}(n^2 + m) , because it consists of two blocks of complexity O(n2)\mathcal{O}(n^2) and O(m)\mathcal{O}(m) , and neither of them is a lower order function with respect to the other.

我个人对这段话的理解是因为两个模块都不是相对于另一个的低阶函数。但 n2n^2 的次数是 2, mm 的次数是 1,难道不是 n2n^2 的次数比 mm 的次数要大吗?

请大佬解惑为什么这段代码是 O(n2+m)\mathcal{O}(n^2 + m) 的,而不是 O(n2)\mathcal{O}(n^2) 的,谢谢。

2022/1/28 11:09
加载中...