mxqz 时间复杂度
  • 板块学术版
  • 楼主August_Light
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/6/18 11:01
  • 上次更新2023/10/23 12:52:09
查看原帖
mxqz 时间复杂度
589916
August_Light楼主2023/6/18 11:01

对时间复杂度有两个问题。QwQ

关于 OO 和 Θ\Theta

SPFA 的时间复杂度是 O(nm)O(nm)。

  1. 可以说它的时间复杂度是 O(n114m514)O(n^{114}m^{514}) 吗?
  2. 可以说它的时间复杂度是 Θ(nm)\Theta(nm) 吗?

关于化简

我有一个算法的时间复杂度是 O(nlog⁡n+nlog⁡m+mlog⁡m)O(n \log n + n \log m + m \log m)。

当 n<mn < m 时,可知 nlog⁡m<mlog⁡mn \log m < m \log m。

当 n>mn > m 时,可知 nlog⁡m<nlog⁡nn \log m < n \log n。

是否可以因此将原时间复杂度记为 O(nlog⁡n+mlog⁡m)O(n \log n + m \log m)?

2023/6/18 11:01
加载中...