다항식을 power n 알고리즘

다항식 함수를 수행하는 가장 좋은 방법은 무엇입니까? O (?) 또는 FFT (fast Fourier transformation)에 의해 다항 정리 (wikipedia)를 취한 다음 O ((N * log (N))^2)로 역 FFT를 수행합니까?다항식을 power n 알고리즘

출처

2013-12-23 user2076517

당신이 예제를 만들 수 있습니다 : 여기

는 몇 가지 참신한 응용 프로그램과 더 나은 설명이다? 너는 무엇을 계산하고 싶니? – duedl0r

가장 좋은 방법은 무엇입니까? 문제의 크기/순서는 무엇입니까? 가능성이 가장 높은 답변이 하나 있습니다. 예를 들어, 작은 문제의 경우, 알고리즘의 초기 설정이 속도 향상에 가치가 없기 때문에 직선적 인 brute-force 곱셈은 FFT 기반 알고리즘을 사용하는 것보다 빠를 수 있습니다. 하지만 거대한 문제의 경우, FFT 접근법은 확실히 가치가있을 것입니다 ... – twalberg

왜 FFT + 역 FFT가 O ((N log (N))^2)라고 생각합니까? 둘 다 O (N log (N))이므로 이들의 합 또한 O (N log (N))입니다. – sebii

FFT를 자주 사용해야하거나 큰 다항식을 사용해야하는 경우. 순진 곱셈 알고리즘은 O (N^2)이고 FFT는 O (Nlog (N))입니다. JeffE FFT

출처

2013-12-24 06:15:07 sebii

p (z)^k가 계산되어야한다면 두 경우 모두 N = k * deg (p)가됩니다. p의 뿌리의 힘을 뿌리로 가지는 다항식을 계산하려면 Dandelin-Graeffe 반복을 사용하거나 비 2 계의 힘을 사용하려면 뿌리와 다항식 계수의 힘 합계 사이의 뉴튼 ID를 사용하십시오. – LutzL

답변

관련 문제