需要一些 help/confirmation 一段时间和 space Java 中的复杂性问题

Question

我想确保我处理 space 复杂性和时间的方式是好的。我是一名 IT 学生，我正在兼职工作，除了我正在为我工作的公司学习的课程之外，我还得到了这个练习，我想知道我是否正确地处理了复杂性，或者我是否在曲目错误！

我想弄清楚两个案例的时间和 space 复杂度。我已经采取了一些步骤并进行了很好的尝试，所以在下面你会发现我对 Java 代码中三个不同 methods/functions 的想法和答案。向下滚动以查看练习。

案例 1：

  public int func1(int n) {

   int total = 0;
     for (int i = 0; i < n; i++) {
      for (int j = 50; j > 0; j--) {
       for (int k = 0; k < j/2; k++) {
        total++;
       }
      }
     }
     return sum;
    }

时间复杂度
对于时间复杂度，我认为外循环是 O(n)，中间循环是 O(1)，最内循环也是 O(1)，因为它与第一个循环无关，所以我是否正确是大 O(1 * 1 * n) => 大 O(n)??

Space复杂度
Space 这个的复杂度可能是大 O(1)，因为循环中没有实例化新变量。只有循环本身和 int total = 0。但这也与 n 无关.所以我猜 Space 是 Big O(1).

案例二：

  public int func2(int n) {
      if (n > 0) {
      int[] array = new int[n+n];
      return func2(n-1) + func2(n-2);
     } else {
      return 0;
     }
    }

时间复杂度
这个的时间复杂度对我来说有点难，因为一开始是数组。我认为因为循环中的递归，n 输入的复杂度很重要，所以它是大 O(n) 时间复杂度.但我不确定它是否可能是 n^2，因为 return 双递归 func2(n-1) + func2(n-2).. 我在 Big O(n) 上的方向正确吗？

Space复杂度
对于最后一个，我认为这种情况下的 space 复杂度是 2n，那么 n 是多少？因为每次调用该函数时，都会创建一个长度为 2n 的新数组，所以如果 n=4，则数组长度为 8，然后下一次迭代为 6，依此类推。

所以我的最终答案是 space 复杂度的大 O(n)。

Answer 1

你对第一种情况的分析是正确的。

第二种情况比较难。你不能真正准确地评估时间复杂度，因为：

肯定是n的指数；
如果你需要一个严格的复杂性界限，你必须得到完全正确的基数和指数；和
您真的不知道分配需要多长时间。在某些系统中，它是 O(n)，因为为了安全起见，内存将被清零。在某些情况下，它将被 O(n) 摊销，因为正在使用复制垃圾收集器。在某些情况下，它是不确定的，因为必须遍历一些空闲列表。

A safe-ish 假设分配需要 O(n)，但您的教授可能期望分配为 O(1)。通常差异无关紧要，因为您使用了分配的所有内存。 O(1) 分配导致递归关系 T(n) = O(1) + T(n-1) + T(n-2)。这是一个斐波那契数列，所以复杂度是 O(ⁿ)，其中是黄金比例。

space 复杂度是同时分配的总内存。同样，这取决于实现细节，但我们可以假设您使用的是不需要释放内存的 garbage-collected 语言，否则您将因不释放内存而犯下可怕的错误。所以...

因为分配的数组没有在任何地方使用，所以没有对它的引用，所以如果语言是垃圾收集那么 space 复杂度将为 O(n)，因为数组可能是垃圾分配后立即收集。

需要一些 help/confirmation 一段时间和 space Java 中的复杂性问题

Need some help/confirmation for some time and space complexity problems in Java

algorithm

data-structures

time-complexity

space-complexity