Блог

Я решил задачу 12 проекта Эйлера и попытался оптимизировать свое решение.
Часть, на которой я сосредотачиваюсь, — это часть нахождения числа делителей.
Я думал, что первый алгоритм, который я создал, будет медленнее, чем второй, но это не так, и я не понимаю, почему?

Первый (обычный подсчет идет до n ** 0.5):

 from math import sqrt
def get(n):
    count = 0
    limit = sqrt(n)
    for i in range(1,int(limit) 1):
        if n%i==0:
            count =2
    if limit.is_integer():
        return count-1
    return count
  

Во-вторых (разложение на простые множители, чтобы получить каждую степень каждого простого числа, чтобы использовать эту формулу, я использую форму простых чисел, как вы можете видеть здесь, чтобы вычислять быстрее, но это все еще медленнее).:

 def Get_Devisors_Amount(n):#Prime factorization
    if n <=1: return 1
    dcount = 1
    count = 0
    while n%2==0:
        count =1
        n//=2
    dcount*=(count 1)
    
    count = 0
    while n%3==0:
        count =1
        n//=3
    dcount*=(count 1)
    
    i = 1#count for the form of primes 6n -1
    while n!=1:
        t = 6*i 1
        count = 0
        while n%t==0:
            count =1
            n//=t
        dcount*=(count 1)
        t = 6*i-1
        count = 0
        while n%t==0:
            count =1
            n//=t
        if count!=0:
            dcount*=(count 1)
        i =1
        if dcount==1: return 2# n is a prime
    return dcount
  

Как я проверял время

 import time
start = time.time()
for i in range(1,1000):
    get(i)

print(time.time()-start)


start = time.time()
for i in range(1,1000):
    Get_Devisors_Amount(i)

print(time.time()-start)
  

Вывод:
получаем: 0.00299835205078125
Get_Devisors_Amount: 0.009994029998779297

Хотя я использую свойство и формулу, которые, я думаю, должны сократить время поиска, первый метод все равно быстрее. не могли бы вы объяснить мне, почему?

В первом подходе вы проверяете делимость с каждым числом от 1 до sqrt(x) , поэтому сложность тестирования одного числа такова sqrt(x) . Согласно этой формуле, сумма первых n корней может быть приближена к n*sqrt(n) .
Временная сложность метода 1: O(N*sqrt(N)) (N — общее количество проверяемых чисел).

Во втором подходе есть 2 случая:

1. Если число не является простым, проверяются все простые числа до n . Сложность — O(n/6) = O(n)
2. Если число простое, мы можем приблизить сложность O(log(n)) (для этого случая может быть более точный расчет сложности, я делаю приближение, поскольку это не имеет значения в доказательстве)

Для простых чисел, используя тот факт, что мы проверяем их с (n/6) помощью простых чисел, сложность станет 5/6 7/6 11/6 13/6 17/6 ..... (last prime before n)/6 . (sum of all prime numbers till n)/6 На данный момент это можно свести к. Теперь сумма всех простых чисел до N может быть аппроксимирована как N^2/(2*logN) . Таким образом, сложность для этого шага становится N^2/(6*(2*logN)) = N^2/(12*lognN) .

Временная сложность метода 2: O(N^2/(12*lognN)) (N — общее количество проверяемых чисел).

(если вы хотите, вы можете сделать более точные оценки для временных сложностей каждого шага. Я сделал несколько приближений, поскольку это помогает доказать точку зрения, не делая никаких чрезмерно оптимистичных предположений).

Ваш первый алгоритм разумно учитывает только делители до sqrt (n) .

Но ваш второй алгоритм учитывает делители вплоть до n, хотя, по общему признанию, если n имеет много факторов, n будет уменьшено на этом пути.

Если вы исправите это в своем алгоритме, изменив это:

 t = 6*i-1
  

к этому:

 t = 6*i-1
if t*t > n:
  return dcount * 2
  

Тогда ваш второй алгоритм будет быстрее.

( * 2 Это потому, что алгоритм в конечном итоге найдет оставшийся простой множитель (сам n), а затем dcount *= (count 1) удвоит dcount перед его возвратом.)