Какова сложность операций на BigInteger в Java 7?
Какова сложность методов multiply, divide а также pow в BigInteger В настоящее время? Там нет упоминания о вычислительной сложности в документации (нигде больше).
3 ответа
Если вы посмотрите на код для BigInteger (предоставляется JDK), мне кажется, чтоmultiply(..) имеет O(N ^ 2) (на самом деле метод multiplyToLen(..)). Код для других методов немного сложнее, но вы можете увидеть сами.
Примечание: это для Java 6. Я предполагаю, что это не будет отличаться в Java 7.
Как отмечено в комментариях к ответу @Bozho, Java 8 и более поздние версии используют более эффективные алгоритмы для реализации умножения и деления, чем наивные
O(N^2) алгоритмы в Java 7 и ранее.
Умножение в Java 8 адаптивно использует либо наивный
O(N^2)алгоритм длинного умножения, алгоритм Карацубы или трехсторонний алгоритм Тоома-Кука в зависимости от размеров перемножаемых чисел. Последние (соответственно)
O(N^1.58) и
O(N^1.46).
Разделение Java 8 адаптивно использует либо
O(N^2)алгоритм деления в столбик или алгоритм Бурникеля-Циглера. (Согласно исследованию, последний
2K(N) + O(NlogN) для деления 2N-значного числа на N-значное число, где
K(N) время умножения Карацубы для двух N-значных чисел.)
Также были оптимизированы некоторые другие операции.
Нет упоминания о вычислительной сложности ни в документации (ни где-либо еще).
Некоторые подробности сложности упомянуты в исходном коде Java 8. Причина, по которой в документации javadoc не упоминается сложность, заключается в том, что она зависит от реализации как в теории, так и на практике. (Об этом свидетельствует тот факт, что сложность некоторых операций значительно различается между Java 7 и 8.)
Существует новый "лучший" класс BigInteger, который не используется Sun JDK для консервативности и отсутствия полезных регрессионных тестов (огромные наборы данных). Парень, который сделал лучшие алгоритмы, возможно, обсуждал старого BigInteger в комментариях.
Измерь это. Выполните операции с линейно увеличивающимися операндами и начертите время на диаграмме. Не забудьте прогреть JVM (несколько прогонов), чтобы получить достоверные результаты тестов.
Если операции линейные O (n), квадратичные O(n^2), полиномиальные или экспоненциальные, то они должны быть очевидными.
РЕДАКТИРОВАТЬ: Хотя вы можете дать алгоритмы теоретические границы, они не могут быть такими полезными на практике. Прежде всего, сложность не дает фактора. Некоторые линейные или субквадратичные алгоритмы просто бесполезны, потому что они потребляют так много времени и ресурсов, что их недостаточно для решения поставленной задачи (например, умножение матрицы Копперсмита-Винограда). Тогда ваши вычисления могут иметь все клуджи, которые вы можете обнаружить только экспериментально. Есть готовые алгоритмы, которые ничего не делают для решения проблемы, но для ускорения реального решателя (матричная обработка). Есть субоптимальные реализации. При увеличении длины ваша скорость может резко упасть (отсутствует кеш, перемещение памяти и т. Д.). Поэтому для практических целей советую заняться экспериментами.
Лучше всего удваивать каждый раз длину ввода и сравнивать время. И да, вы узнаете, если алгоритм имеет n^1.5 или n^1.8 сложности. Просто увеличьте длину ввода в четыре раза, и вам нужно только половину времени для 1,5 вместо 2. Вы снова получите почти половину времени для 1,8, если умножить длину на 256 раз.