Минимальная сложность для умножения 2 связанных списков, представляющих очень большие числа?

Question

У меня есть 2 связанных списка, представляющих очень большие числа (которые не могут быть сохранены ни в чем другом, кроме связанного списка). у меня есть метод Add со сложностью O (n). я хотел знать, возможно ли каким-либо образом умножить 2 числа БЕЗ конвертирования всего списка в String / int / long (вычислить по списку, если это возможно), и сохранить его на сложности O(n^2),

на данный момент, что бы я ни пытался, я дошел до сложности O(n^3), и это не достаточно хорошо.

Спасибо за помощь.

Answer 1

Алгоритм "длинного умножения", который большинство западных студентов изучают в школе, уже дает вам сложность O(n²), поэтому, возможно, вы могли бы объяснить, какой алгоритм вы используете.

Существуют алгоритмы с меньшей сложностью: алгоритм Карацубы, Тома-Кука и Шёнхаге-Штрассена. Последний имеет наименьшую из известных на сегодняшний день сложность, O(n log n log log n), но могут быть еще лучшие алгоритмы, которые еще предстоит обнаружить.