Временная сложность печати простых чисел в пределах определенного диапазона?

Question

Я написал ответ на этот вопрос, в котором спрашивается о следующем:

Какова временная сложность для данного кода, который выводит простые числа из start к end?Это $O(конец*\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);
}

Уведомление:Это не мой код.Это по махеш87.

Мой ответ на это таков:

---

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

Как мы определили $n$, очевидно , что printPrimeSeries это просто $O(n)$ (из 0 к end).Метод использует findPrimeOrNot который повторяется из 2 к Math.sqrt(n), который является $O(\sqrt{n})$.Сочетание того и другого - это $O(n)O(\sqrt{n})$, который просто $O(n\sqrt{n})$.

Обратите внимание, что $O$ обозначение говорит вам кое-что об асимптотическом поведении алгоритма.Это не имеет большого значения, если есть 2 параметра, по крайней мере, в данном случае.

Так что да, ваше предположение полностью верно (игнорируя то, что вы написали end вместо $n$).

---

Другие пользователи предположили, что правильным ответом будет $O((end - start)\sqrt{end})$.Я думаю, что это обоснованная точка зрения, но она не дает никакой полезной информации с точки зрения $O$ обозначение для данного случая.

Теперь мой вопрос:Каков формально правильный способ описания временной сложности данного алгоритма?Верны ли мои рассуждения или они просто ошибочны?

Answer 1

И то, и другое "временная сложность равна $O( end \cdot \sqrt{конец} )$" и "временная сложность равна $O( (начало-конец) \cdot \sqrt{конец} )$" являются правильными утверждениями (при условии, что арифметические операции с задействованными целыми числами могут выполняться за постоянное время).

В некоторых случаях вторая верхняя граница более жесткая.Например, установка $начало=конец-10$ первый верхний остается неизменным, в то время как второй упрощается до $O(\sqrt{end})$.

Также обратите внимание, что "В 𝑂 обозначении 𝑛 представляет размер проблемы, который в вашем случае представляет собой диапазон между началом и концом." является ложным.Размер (любая разумная кодировка) экземпляра равен $O(\конец журнала)$.

Answer 2

Ваша функция findPrimeOrNot(n) выполняется в $O(n^{1/2})$ в худшем случае.Часто время выполнения сокращается.Например, для четных чисел n функция возвращает значение после одного деления.Но для простых чисел, где проверяются все делители вплоть до sqrt(n), время выполнения действительно равно $\Тета(n^{1/2})$.И вероятность того, что случайное целое число x является простым, равна примерно x / log x.

Вам нужно было бы проверить, каково именно среднее количество делений.С вашим алгоритмом, который может быть улучшен, количество делений составляет, по крайней мере, около (end - start) * sqrt (n) / log n и, самое большее, около (end - start) * sqrt (n) делений.

Если вы хотите напечатать простые числа, вы обнаружите, что печать имеет такой большой постоянный коэффициент, что время выполнения печати около (end - start) / log n простых чисел намного больше, чем время печати простых чисел для любого разумного диапазона простых чисел.