Как домашнее задание, я должен реализовать целочисленное умножение на числа 1000 цифр, используя подход «разделяй и властвуй», который работает ниже O (n).Какой алгоритм мне следует изучить?
Взгляните на алгоритм Карацубы . Он включает шаг рекурсии, который вы можете легко смоделировать с помощью метода «разделяй и властвуй».
Алгоритм Шёнхаге-Штрассена - один из самых быстрых известных алгоритмов умножения.Это занимает O (n log n log log n) времени.
Алгоритм Фюрера является самым быстрым из известных алгоритмов умножения больших чисел и занимает O (n * log n * 2 O (log * n) ) времени.
Я не думаю, что какой-либо алгоритм умножения мог бы принимать значение, меньшее или даже равное O (n).Это просто невозможно.