집합 구성원의 GCD를 재귀 적으로 계산합니다.

Question

우리는 양의 정수 집합을가집니다.

이 세트의 모든 가능한 정수 쌍 중 최대 공약수를 계산하여 새 세트를 만듭니다.

집합에 구성원이 하나만 남을 때까지 위의 단계를 다시 실행합니다.

이 프로세스가 생성하는 새 집합 수와 마지막 집합의 구성원이 1인지 계산하는 O (n) 메서드가 있습니까?

내가 설명한 프로세스를 보여주는 일부 파이썬 코드.

from itertools import combinations 
from fractions import gcd 
import random 

def gen_new_set(a): 
    count = 0 
    while len(a) != 0: 
     print str(count)+':\t'+str(len(a))+'\t'+str(a) 
     a = set(gcd(x[0], x[1]) for x in combinations(a,2)) 
     count += 1 

if __name__ == '__main__': 
    a = set(random.sample(range(1,40), 10)) 
    gen_new_set(a) 

Answer 1

호는 첫 번째 반복에서 O(n*n)쌍 있는데, 그 중 하나가 다른 곳 공유되는 공통의 소인수를하는 것이 가능하다. 따라서 일반적으로 집합 S가 1 또는 2 인 수의 차이를 알리는 데 필요한 작업량은 O(n*n)입니다.

물론 O(n) 알고리즘을 통해 전체 집합의 GCD를 찾을 수 있습니다. 당신은 전체 세트가 1이라면 당신에게 물어보십시오.

이제 "정수"라고 말하면, 임의의 정수는 분해하기가 극도로 어려울 수 있습니다 (암호화가 잘 활용한다는 사실). 그러나 정수가 합리적인 크기라면 인수 분해는 실제로 매우 효율적인 연산이며 정수 당 소수 요소는 거의 없습니다. 따라서 전처리 단계로서 인수 분해의 관계를 저장할 수 있습니다. 그런 다음 해시 테이블을 각 프라임 p을 나누는 숫자에 매핑합니다. 이제는 소수를 따라 가며, 각각은 나누는 것들의 부분 집합을 꺼내고, 그 부분에 대한 계산을 재귀 적으로 수행하는 것이 간단합니다. n 정수의 수이다

이 알고리즘은 O(n*k + n*s) 같은 것으로 해결해야 k 그들을 인수 분해의 평균 비용이며, s는 생성 부분 집합의 수입니다. 어느 비트 n 및 작은 정수에 대해 설명하는 작업을 수행하는 것보다 효율적입니다.