Какова сложность операций на BigInteger в Java 7? - PullRequest
7 голосов
/ 28 января 2010

Какова сложность методов multiply, divide и pow в BigInteger в настоящее время? В документации (и где-либо еще) нет упоминания о сложности вычислений.

Ответы [ 3 ]

3 голосов
/ 28 января 2010

Если вы посмотрите на код для BigInteger (поставляется с JDK), мне кажется, что multiply(..) имеет O (n ^ 2) (на самом деле метод multiplyToLen(..)). Код для других методов немного сложнее, но вы можете видеть сами.

Примечание: это для Java 6. Я полагаю, что это не будет отличаться в Java 7.

2 голосов
/ 16 марта 2010

Существует новый "лучший" класс BigInteger, который не используется Sun JDK для консервативности и отсутствия полезных регрессионных тестов (огромные наборы данных). Парень, который сделал лучшие алгоритмы, возможно, обсуждал старого BigInteger в комментариях.

Вот, пожалуйста, http://futureboy.us/temp/BigInteger.java

2 голосов
/ 28 января 2010

Измерь это. Выполните операции с линейно увеличивающимися операндами и начертите время на диаграмме. Не забудьте прогреть JVM (несколько прогонов), чтобы получить действительные результаты тестов.

Если операции линейные O (n), квадратичные O (n ^ 2), полиномиальные или экспоненциальные должны быть очевидными.

РЕДАКТИРОВАТЬ: Хотя вы можете дать алгоритмы теоретические границы, они не могут быть такими полезными на практике. Прежде всего, сложность не дает фактора. Некоторые линейные или субквадратичные алгоритмы просто бесполезны, потому что они потребляют так много времени и ресурсов, что их недостаточно для решения задачи (например, умножение матрицы Копперсмит-Винограда). Тогда ваши вычисления могут иметь все клуджи, которые вы можете обнаружить только экспериментально. Есть готовые алгоритмы, которые ничего не делают для решения проблемы, но для ускорения реального решателя (матричная обработка). Существуют неоптимальные реализации. При увеличении длины ваша скорость может резко упасть (отсутствует кеш, перемещение памяти и т. Д.). Поэтому для практических целей советую заняться экспериментами.

Лучше всего удваивать каждый раз длину ввода и сравнивать времена. И да, вы действительно узнаете, имеет ли алгоритм n ^ 1,5 или n ^ 1,8 сложности. Просто четверной длина ввода и вам нужно только половину времени для 1,5 вместо 2. Вы снова получаете почти половину времени для 1,8, если умножить длину на 256 раз.

...