Java 7 BigInteger의 연산은 얼마나 복잡합니까?

방법이 얼마나 복잡합니까? multiply, divide 및 pow은 BigInteger에 현재 있습니까? 문서의 계산상의 복잡성에 대한 언급은 없습니다 (다른 곳에서도 마찬가지입니다). 당신이 (JDK와 함께 제공) BigInteger의 코드를 보면Java 7 BigInteger의 연산은 얼마나 복잡합니까?

출처

2010-01-28 Anonymous

소스 코드를 확인할 수 있습니다. – uckelman

사실 저는 이미 시도했습니다. 그러나 많은 지식 없이는 분석하기가 매우 어려워 보입니다. StackOverflow를 읽는 누군가가 그 지식을 가지기를 바랍니다. 아마 너무 낙관적 인 것일까? –

Java 7에 대해 언급하는 특별한 이유가 있습니까? 'BigInteger'는 Java 1.1부터 존재합니다. –

, multiply(..)가 (실제로이 방법은 multiplyToLen(..)입니다) O (N^2)을 가지고 나에게 나타납니다. 다른 메소드의 코드는 좀 더 복잡하지만 직접 볼 수 있습니다.

참고 :이 내가 그것을 측정이

출처

2010-01-28 11:42:04 Bozho

몇 가지 복잡도가 있습니다 : http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations ... O (n^1.585) 또는 O (n^1.465)를 제외하고 O (n^2)를 말할 수 있습니까? – Joey

Java 7에서 변경된 부분이 있다고 생각합니다. 검색 한 내용은 기억이 나지 않지만 부족합니다. –

Rössel : 곱셈을위한 _exist_ 다른 알고리즘이 있지만 Java 6에서는 이러한 알고리즘을 사용하지 않습니다. 큰 숫자를 곱하면 확실히 교과서 알고리즘과 Karatsuba 곱셈의 차이를 알 수 있습니다. 주 메모리에 숫자를 채우지 않는 한 다른 점프는 점프가 적습니다. – Charles

자바 7에 차이가 없습니다 가정 자바 6을위한 것입니다. 직선적으로 증가하는 피연산자로 연산을 수행하고 다이어그램에 시간을 그립니다. 유효한 벤치 마크 결과를 얻으려면 JVM을 워밍업 (여러 번 실행)하는 것을 잊지 마십시오.

연산이 선형 O (n)이면 2 차 O (n^2), 다항식 또는 지수가 분명해야합니다.

편집 : 이론적 인 경계 알고리즘을 제공 할 수 있지만 실제로 유용하지 않을 수 있습니다. 우선, 복잡성은 요인을주지 않습니다. 일부 선형 또는 하위 쿼드 러리 알고리즘은 너무나 많은 시간과 리소스를 먹어서 문제가되지 않는 경우 유용합니다 (예 : Coppersmith-Winograd 행렬 곱셈). 그러면 계산으로는 실험으로 만 찾을 수있는 모든 불투명 함이있을 수 있습니다. 문제를 해결하는 것이 아니라 실제 솔버 (매트릭스 조절)를 빠르게하는 알고리즘을 준비하고 있습니다. 차선의 구현이 있습니다. 길이가 길어지면 속도가 크게 떨어질 수 있습니다 (캐시 누락, 메모리 이동 등). 실용적인 목적으로, 나는 실험을 할 것을 권합니다.

가장 좋은 방법은 입력 시간을 두 배로 늘려 시간을 비교하는 것입니다. 그리고 예, 당신 알고리즘이 n^1.5 또는 n^1.8 복잡성을 가지고 있는지 알아보십시오. 단순히 입력 길이를 4 배로하고 2 대신 1.5로 반 시간 만 필요합니다. 길이를 256 배로 늘리면 1.8의 시간이 거의 절반이됩니다.

출처

2010-01-28 11:42:17

를 참조하십시오. 큰 값의 n을 테스트해야합니다. 두 개의 n 비트 BigIntegers (t_0)와 두 개의 2n 비트 BigIntegers (t_1)를 곱하는 시간을 측정 한 경우 그러면 복잡성이 O (n^(log2 (t_1/t_0)))가 될 것입니다. 일반적으로 나는 (아마도 불공정하게) 경험적 방법에 조금 회의적이다. –

그러나 이것은 어려운 접근 방법입니다. 따라서 알고리즘의 조합보다는 단일 알고리즘이 사용된다고 생각할 필요는 없습니다. 따라서 10 자리에서 1000 자리까지의 비율은 1000 자리에서 3000 자리까지의 비율과 다를 수 있습니다. – Charles

sunjdk에서 보수주의와 유용한 회귀 테스트 (거대한 데이터 세트)가 부족하지 않은 새로운 "더 좋은"BigInteger 클래스가 있습니다. 더 나은 알고리즘을 수행 한 사람은 댓글에서 이전 BigInteger에 대해 논의했을 것입니다.

여기 있습니다. http://futureboy.us/temp/BigInteger.java

출처

2010-03-16 01:37:33 i30817

Java 7 BigInteger의 연산은 얼마나 복잡합니까?

답변

관련 문제