Помогите оценить сложность алгоритма
from math import log2, gcd
a = 2**30
b = 2**31
all_simple = []
all_log2 = []
all_paras = []
all_paras2 = []
final_paras = []
paras_counter = 0
def is_prime(num):
if num == 1:
return False
for p in range(2, int(num**0.5)+1):
if num % p == 0:
return False
return True
for i in range(a, b+1):
if is_prime(i):
all_simple.append(i)
Ответы (1 шт):
Автор решения: Suspicio
→ Ссылка
O(n*sqrt (n)), поскольку время вызова is_prime(i) осуществляется (b-a) раз, где i находится между [a, b] и работает во время sqrt(i), если будем считать в общих случаях исключая все переменные, то это и будет худшим временем.
Реальное время намного ниже, поскольку оно пропускает много чисел за 1 или 2 операции, поэтому сложность в реальном времени составляет около O (n + (количество простых чисел) * sqrt (n)), вы можете исследовать эту тему, чтобы достичь строгой формулы.