Какова сложность моего кода, который печатает простые числа в диапазоне? - PullRequest
Новая
       48

Какова сложность моего кода, который печатает простые числа в диапазоне?

1 голос
/ 13 июля 2020

Этот код печатает все простые числа от start до end в зависимости от ввода пользователя.

Какова его сложность? Это O(end * sqrt(n))? 

/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

Ответы [ 2 ]

2 голосов
/ 13 июля 2020

Двигаясь шаг за шагом, для краткости, давайте назовем ваше начальное значение m и закончим как n:

  • printPrimeSeries метод линейно связан с n - m
  • Для каждого элемента в указанном выше диапазоне сложность внутреннего l oop составляет sqrt(n) - 2. Без учета константы это sqrt(n)

Таким образом, сложность выглядит как O((n - m) * sqrt(n)).

0 голосов
/ 13 июля 2020

Общая сложность: O (конец - начало) * sqrt (конец)) . FYI: Я показываю вам альтернативную оценку, которая не так точна:

В O -нотации вас интересует худший случай, поэтому мы можем предположить, что start всегда равно 0. Теперь для анализа нам понадобится только end.

Метод printPrimeSeries - это просто O (конец) , от 0 до end. Метод использует findPrimeOrNot, который выполняет итерацию от 2 до Math.sqrt(n), что составляет O (sqrt (n)) . Максимальное значение для n - это значение end, поэтому для наших целей мы можем назвать сложность O (sqrt (end)) . Объединение обоих: O (конец) * O (sqrt (end)) , что всего лишь O (end sqrt (end)) .

Есть интересные детали к вопросу о распределении простых чисел. Об этом можно прочитать здесь .

...