Временная сложность печати простых чисел в пределах определенного диапазона?
-
29-09-2020 - |
Вопрос
Я написал ответ на этот вопрос, в котором спрашивается о следующем:
Какова временная сложность для данного кода, который выводит простые числа из 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$ обозначение для данного случая.
Теперь мой вопрос:Каков формально правильный способ описания временной сложности данного алгоритма?Верны ли мои рассуждения или они просто ошибочны?
Решение
И то, и другое "временная сложность равна $O( end \cdot \sqrt{конец} )$" и "временная сложность равна $O( (начало-конец) \cdot \sqrt{конец} )$" являются правильными утверждениями (при условии, что арифметические операции с задействованными целыми числами могут выполняться за постоянное время).
В некоторых случаях вторая верхняя граница более жесткая.Например, установка $начало=конец-10$ первый верхний остается неизменным, в то время как второй упрощается до $O(\sqrt{end})$.
Также обратите внимание, что "В 𝑂 обозначении 𝑛 представляет размер проблемы, который в вашем случае представляет собой диапазон между началом и концом." является ложным.Размер (любая разумная кодировка) экземпляра равен $O(\конец журнала)$.
Другие советы
Ваша функция 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 простых чисел намного больше, чем время печати простых чисел для любого разумного диапазона простых чисел.