算法和数据结构——我是否正确地解决了这些复杂性问题？

Question

这是我的第一个 post，所以很抱歉，如果我可以做得更好，请告诉我 ;)

我目前正在练习算法和数据结构，我们需要计算时间和 Space 复杂度。出于某种原因，我发现它很难，如果我走的路是正确的或完全错误的，则无法获得任何 confirmation/guidance 。所以我想我会在这里试一试。

我尝试解决的第一个方法如下：

static void f1(int n) {
 for (int i = 0; i < n; i++) {
    for (int j = i; j < i * i; j++) {
      for (int k = 2; k < j; k++) {
      System.out.println("*");
      }
    }
  }
}

时间复杂度
到目前为止我所做的步骤：第一个for循环的时间复杂度为O(n)，因为i < n，所以迭代n次。第二个 for 循环的时间复杂度为 O(i^2) 因为 j < i*i，它迭代 i^2 次。第三个循环做了 j-2 次，因为 k=2，所以我认为..它是 O(j) 复杂度

所以我不确定以上是否都正确，但现在的步骤是将所有复杂度相乘，所以总复杂度将是 Big O(n * i^2 * j) 然后将是我^2?

因此，如果我做对了，那将是 Big O (i^2) 时间复杂度。

Space复杂度
我不太确定如何从 space 复杂性开始，但我猜它只是大 O(j)，因为它只保存函数调用和 for 循环，即 O(1) 和打印最后一个 for 循环的第 j - 2 次调用了打印行。
我完全不确定这是否是正确的思考方式，但如果不是，我知道也有好处 ;)

在此先感谢您的帮助！

亲切的问候

Answer 1

您的答案可能不正确，因为它们提到了输入中未出现的变量 i 和 j。显然，任何正确答案都必须只提到 n.

outer-most 循环的迭代计数在 n 中呈线性增长，而两个内部循环的迭代计数都随 n^2 增长，因此嵌套在一起的三个循环是 O(n^5)。由于 println 语句的参数独立于 n，它是 O(1)，因此我们总共有 O(n^5) 的时间复杂度。

至于space复杂度，函数中只声明了三个single-valued计数变量，所以是O(1).

Answer 2

最里面的循环有 O(j) 时间复杂度，对。

现在中间的循环有点棘手了。它从 i 运行到 i^2，并且每次迭代在 j 方面都是线性的。您可以将其表示为Sum[i..i^2] j。这是等差数列的总和。回想一下 Sum[a..b] j = O(b^2 - a^2)。代入极限（a = i, b = i*2）得到中间循环复杂度O((i^2)^2 - i^2) = O(i^4).

最后，外循环从0运行到n，每次迭代为O(i^4)。重要的是要知道 k 次多项式的总和产生 k+1 次多项式。也就是说整个函数的时间复杂度是O(n^5).

关于space的复杂度，不可能是O(j)，因为j是一个自由变量。它不存在于函数之外。尝试证明是O(1).

算法和数据结构——我是否正确地解决了这些复杂性问题？

Algorithms and Datastructures - Am I solving these complexity questions right?

c#

algorithm

time

complexity-theory

space