时间 Complexity/big o 嵌套循环递归的表示法

Question

我在看下面的代码

public class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            for (long b = 0; b * b <= c; b++) {
                if (a * a + b * b == c)
                    return true;
            }
        }
        return false;
    }
}

作者说这段代码的时间复杂度是√c。我不明白的是如何。

所以假设我们给出一个 c=20 的例子。那么代码将运行 15 次但是 √20=4.47

Answer 1

您的最大条件是

a * a <= c

和

b * b <= c

如果你对两边都取平方根，你会得到 a <= √c & b <= √c

因此，如果您针对性能优化代码...
（即不要在每次迭代时计算最大值！）
...看起来像这样：

public boolean judgeSquareSum(final int c) {

    final long rootC = (long) Math.sqrt(c);

    for (    long a = 0; a <= rootC; a++) {
        for (long b = 0; b <= rootC; b++) {

            if (a * a + b * b == c) {
                return true;
            }
        }
    }
    return false;
}

所以现在你明白了√c 的复杂性声明从何而来。

Answer 2

这可以进一步优化为：

public boolean judgeSquareSum(final int c) {

    final long rootC = (long) Math.sqrt(c);

    if (c == rootC * rootC) {
        return true;
    }

    for (long a = 0; a <= rootC; a++) {

        final long aSquared = a * a;
        final long b        = (long) Math.sqrt(c - aSquared);

        if (aSquared + b * b == c) {
            return true;
        }
    }
    return false;
}

以上生成的结果与所有 +ve c.

的原始发布结果相同

Answer 3

我只是想看看实际的运行情况。 √c 似乎是最好的情况。我怀疑当 a = 0 和 b * b = c 时会发生这种情况，从而消除了多次运行外循环的需要。

prints:
  i =           10      sqrt =      3   runs =            8
  i =          100      sqrt =     10   runs =           11
  i =        1,000      sqrt =     31   runs =          351
  i =       10,000      sqrt =    100   runs =          101
  i =      100,000      sqrt =    316   runs =        4,121
  i =      500,000      sqrt =    707   runs =       71,501
  i =    1,000,000      sqrt =  1,000   runs =        1,001
  i =    5,000,000      sqrt =  2,236   runs =      521,209
  i =   10,000,000      sqrt =  3,162   runs =      382,721
  i =   50,000,000      sqrt =  7,071   runs =    7,079,001
  i =  100,000,000      sqrt = 10,000   runs =       10,001

印有：

public class WhosebugTest {
  static int counter;

  public static void main(String[] args) {
    print(10);
    print(100);
    print(1000);
    print(10000);
    print(100000);
    print(500000);
    print(1000000);
    print(5000000);
    print(10000000);
    print(50000000);
    print(100000000);
  }

  static void print(int i) {
    new Solution().judgeSquareSum(i);
    String format = "  i = %,12d\tsqrt = %,6d\truns = %,12d\n";
    System.out.printf(format,i,(int)Math.sqrt(i),counter);

  }

  static class Solution { // only added a counter
      public boolean judgeSquareSum(int c) {
          counter = 0;
          for (long a = 0; a * a <= c; a++) {
              for (long b = 0; b * b <= c; b++) {
                  counter++;
                  if (a * a + b * b == c)
                      return true;
              }
          }
          return false;
      }
  }
}

Answer 4

给定的代码段是 O(n) 和 Ω(√n)，这意味着规定的时间复杂度只是最佳情况。

*对数纵轴

Answer 5

换句话说：如果a² + b² = c，极限情况是：

a² + 0² = c（当然是 0² + b² = c，这是类似的）
-> a² = c
-> a = √c

因此，对于任何 b、a <= √c

最初发布的代码每次迭代都会检查 a * a <= c。
仅评估一次极限值被认为是最佳实践（因为它更快）。
正如我们刚刚看到的，a * a <= c 可以重写为 a <= √c

所以for循环可以编码如下：

final long rootC = (long) Math.sqrt(c);

for (long a = 0; a <= rootC; a++) {
    :
    :
}

...我希望这能让原始代码的 √c 复杂性声明变得清晰。

第二个for循环是不必要的，因为b可以凭经验计算

对于任何 a:
a² + b² = c（其中 c 已知）
-> b² = c - a²
-> b = √(c - a²)
（只能接受 b 的整数值）

时间 Complexity/big o 嵌套循环递归的表示法

Time Complexity/big o notation for nested loop recursion

java

big-o

time-complexity

nested-loops