내 의견을 답으로 정리 : 나눗셈은 (사소한) 나눗셈으로 환원 할 수 있고 나눗셈은 (사소하게) 뉴턴의 방법과 같은 접근법을 통해 곱셈으로 나눌 수 있기 때문에 문제는 정수 곱셈과 같은 시간 복잡성을 가져야합니다. AFAIK, 사소한 선형보다 곱셈에 대한 알려진 하한이 없기 때문에 문제에 대해서도 마찬가지입니다. 특히 곱셈은 (본질적으로) 알고리즘, 하한에 대한 희망 은 거의 헛된 것입니다.O(nlognlog∗n)

$O(n\log n\log^* n)$nlognloglogn

$n\log n\log\log n$

나누기가 곱셈에 대한 복잡성을 정확하게 감소시키는 이유는 내가 이해하는 바와 같이 뉴턴의 방법이 서로 다른 확대 크기의 곱셈을 수행하기 때문입니다. 즉, 복잡도 를 사용한 곱셈 알고리즘이 있으면이 곱셈 알고리즘을 중간 단계로 사용하는 나눗셈 알고리즘의 복잡성이 — 토론중인 모든 복잡한 클래스의 경우 입니다.Θ(f(n))

$\Theta(f(n))$Θ(∑lgnk=0f(n2k))

$\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$Θ(f(n))

$\Theta(f(n))$

답변