Какова временная сложность этого алгоритма?Какова сложность этого алгоритма
void prime(int n) {
int i = 2;
while ((n % i) && i <= sqrt(n))
i++;
if (i > sqrt(n))
print(“%d is a prime number\n”, n);
else
print(“%d is not a prime number\n”, n);
}
Раньше я думал неправильно. Эй, это просто O (sqrt (n)) ... Посмотрите, что while выполняется для всех x < = sqrt (n), который делит n. Таким образом, я могу максимально запустить O (sqrt (n)) раз. Так что это O (sqrt (n)). Никаких других факторов.
@ Vincent_Bryan :: извините за то, что вы сделали это как серебро ... проверьте мой ответ сейчас. Это sqrt (n). – coderredoc
Я думаю, что O (sqrt (n)) - худший случай, какой средний случай? –
Сложность приблизительно равна O (sqrt (N)). В некоторых книгах выражается это как O (N 0,5).
Квадратный корень перевычисляет каждую итерацию цикла. Это довольно медленная операция, поэтому она медленнее, чем оптимальная, но только постоянным фактором, поэтому она не влияет на вычислительную сложность.
Поскольку это фиксированный размер C++, да. Хотя sqrt не обязательно должен быть постоянным, если бы это было, например, python или большой целочисленный тип из математической библиотеки. –
Почему вы думаете, что 'n' является простым или не простым, изменит сложность? – Paul
yap, я знаю, что сложность не изменится, несмотря на то, что n является простым или нет. Поэтому я понятия не имею о его сложности. –
Итак, что именно вы спрашиваете? Ваш комментарий прямо противоречит первой строке вашего вопроса. –