包含两个 for 循环的算法的时间复杂度

Question

public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int n = sc.nextInt();
  int m = sc.nextInt();
  int result = 0;

  for (int i=0; i < n; i++) {
    for (int j=m; j > 0; j--)
      result += 1;
    m -= 1;

  }
  System.out.println(result);
}

此题为真题或假题。语句是“当 n 远大于 2m 时，下面程序的时间复杂度是 O(nm)”。对还是错？

题中的时间复杂度是指最坏情况下的时间复杂度。这是我到目前为止所做的：

内循环运行s m次，每次m的值减1。那么内循环的总迭代次数为：m + m - 1 + m - 2 + m - 3 + .... + 3 + 2 + 1.

我们可以认为这是一个等差数列。

则内循环的总迭代次数为：m(m + 1)/2 = (m² + m)/2.

m达到0后，由于n远大于2*m，外层循环会继续运行O(1)时间n-m次。

所以，时间复杂度为：(m² + m)/2 + n - m = O(m²) .

这是解决这个问题的正确方法吗？

Answer 1

不，那是不正确的。首先，这里没有“最坏情况”或“最好情况”之分，因为步数完全由 n 和 m.

决定

正如您所说，问题是 yes/no 问题。所以简单地计算时间复杂度不是解决这个问题的正确方法（顺便说一句，结果是 而不是 O(m^2) - 你不能只删除 n !).

你到最后一步的推理是正确的。正如您正确计算的那样，步骤数是 (m^2 - m)/2 + n（简化后）。问题是：在 n >> 2m 的假设下，(m^2 - m)/2 + n 是集合 O(mn) 的成员吗？

为简单起见忽略常量，让我们记下不等式的假设：

(m^2 - m)/2 + n < nm (eventually, as n, m grow)

现在两边除以 nm 得到等价的不等式

(m - 1)/(2n) + 1/m < 1

根据假设，第一项消失了，所以我们剩下 1/m < 1，随着 m 的增长，这显然是正确的。因此假设是正确的，答案是。

包含两个 for 循环的算法的时间复杂度

Time complexity for an algorithm involving two for loops

complexity-theory

time-complexity