Сложность времени / большая запись для вложенной рекурсии l oop

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. Что я не понимаю, так это как.

Итак, предположим, что мы приводим пример с = 20. тогда код будет выполняться 15 раз, однако √20 = 4.47

Answer 1

Данный фрагмент кода O(n) и Ω(√n), что означает, что заявленная сложность времени является просто наилучшим случаем.

* Логарифмированная вертикальная ось

Answer 2

Я просто хотел увидеть несколько реальных пробежек. √ c кажется наилучшим сценарием. Я подозреваю, что это происходит, когда a = 0 и b * b = c, что устраняет необходимость в нескольких прогонах внешнего l oop.

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 StackOverflowTest {
  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 3

Другими словами: если a² + b² = c, то ограничивающим регистром является:

a² + 0² = c (и, конечно, 0² + b² = c, что аналогично)
-> a² = c
-> a = √c

Итак, для любого b, a <= √c

Первоначально опубликованный код проверяет a * a <= c для каждой итерации.
It считается лучшей практикой (потому что это быстрее) оценивать предельные значения только один раз.
Как мы только что видели, a * a <= c может быть переписан как a <= √c

Так что for-l oop может быть кодируется следующим образом:

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

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

... что, я надеюсь, ясно объясняет требование сложности √ c для исходного кода.

2-й for-l oop не требуется, как b можно рассчитать опытным путем

Для любого a:
a² + b² = c (где известно c)
-> b² = c - a²
-> b = √(c - a²)
(допустимы только целые значения b)

Answer 4

Это может быть дополнительно оптимизировано до:

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 5

Ваши максимальные условия:

a * a <= c

и

b * b <= c

Если вы возьмете квадрат Root с обеих сторон, вы получите 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.