这些代码的时间和 space 复杂度

Question

我刚刚了解了时间和 space 复杂性，但我认为我并没有真正掌握它们。我会提出一些代码，如果你们中的一些人可以告诉我他们的时间和 space 复杂性以及你们如何决定它们，我会很友好地询问。

代码 1

public static int nmKomplex(int n, int m){
     int sum = 0;
     for(int i = 1; i < n; i++)
       for(int j = 1; j < m; i++)
         sum += i * j;
     return sum;
}

代码 2

public static void Schleife3(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j<= n; j++)
         sum += i * j;

    for(int i = 1; i <= n; i++)
       sum += i
}

Answer 1

第一个代码：

public static int nmKomplex(int n, int m){
     int sum = 0;
     for(int i = 1; i < n; i++)
       for(int j = 1; j < m; i++)
         sum += i * j;
     return sum;
}

TL:DR 时间复杂度 O(n * m) | Space 复杂度 O(1)

一个从 i = 1 到 n 的循环乘以另一个从 j=1 到 m 的循环。对于 n > 1，第一个循环执行 (n - 1) 次迭代，第二个循环执行 (m - 1) 次迭代。因此，双循环执行 nm - n - m + 1 次迭代，可以用 O(n * m).

的时间复杂度表示

space 复杂度为 O(1)（即，常数），因为 n 和 m 的增加值并未反映在所用 space 的增加中。

第二个代码：

public static void Schleife3(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j<= n; j++)
         sum += i * j;

    for(int i = 1; i <= n; i++)
       sum += i
}

TL:DR 时间复杂度 O(n^2) | Space 复杂度 O(1)

对于 n > 1，第一个循环执行 n 次迭代乘以第二个循环也执行 n 次迭代加上第三个循环也执行 n 次迭代。因此，时间复杂度为n^2 + n，可以表示为O(n^2).

space 复杂度为 O(1)（即，常数），因为输入 n 的增加不会反映在使用的 space 增加。

这些代码的时间和 space 复杂度

Time and space complexity of these codes

big-o

time-complexity

space-complexity