Какая сложность операций на Biginteger Java 7?
https://stackoverflow.com/questions/2154117
-
23-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Какая сложность методов multiply, divide а также pow в BigInteger В данный момент? В документации нет упоминания о сложности вычислительной работы (и нигде).
Решение
Если вы посмотрите на код на BigInteger (предоставлено JDK), мне кажется, чтоmultiply(..) имеет O (n^2) (На самом деле метод multiplyToLen(..)) Код для других методов немного сложнее, но вы можете увидеть себя.
Примечание: это для Java 6. Я предполагаю, что это не отличается от Java 7.
Другие советы
Существует новый класс Biginteger, который не используется Sun JDK для консерватизма и отсутствия полезных регрессионных тестов (огромные наборы данных). Парень, который сделал лучшие алгоритмы, мог обсудить старый Biginteger в комментариях.
Измерить это. Сделайте операции с линейно увеличивающимися операндами и нарисуйте время на диаграмме. Не забудьте согреть JVM (несколько пробежек), чтобы получить действительные результаты.
Если операции являются линейными o (n), квадратично O (n^2), полиномиальные или экспоненциальные должны быть очевидны.
РЕДАКТИРОВАТЬ: Хотя вы можете дать алгоритмы теоретические границы, они могут не быть такими полезными на практике. Прежде всего, сложность не дает фактора. Некоторые линейные или субвадратические алгоритмы просто не полезны, потому что они едят так много времени и ресурсов, что они не являются адекватными для проблемы под рукой (например, умножение матрицы Coppersmith-Winograd). Тогда ваши вычисления могут иметь все Kludges, которые вы можете обнаружить только по эксперименту. Существуют алгоритмы, которые не делают ничего, чтобы решить проблему, кроме как ускорить настоящий решатель (кондиционирование матрицы). Существуют неоптимальные реализации. С более длинной длиной ваша скорость может резко упасть (кеш отсутствует, перемещение памяти и т. Д.). Итак, для практических целей я советую провести эксперименты.
Лучше всего удвоить каждый раз, когда длину ввода и сравнивать время. И да, ты делать Узнайте, имеет ли алгоритм сложности n^1,5 или n^1.8. Просто в четыре раза вкладывает длину входа, и вам нужен только половина времени для 1,5 вместо 2. Вы снова получаете почти половину времени на 1,8, если вы умножите длину 256 раз.
