Като домашна работа, трябва да приложа цяло число на 1000 цифри, като използвам подход на разделяне и завладяване, който работи под O (n). Какъв алгоритъм трябва да разгледам?
Отговори:
2 за отговор № 1Schönhage-Strassen алгоритъм е един от най-бързите алгоритми за размножаване, известни. Това отнема O (n log n log log n) време.
Алгоритъм на Фюрер е известен досега алгоритъм за размножаване с най-бързи числа и приема O (n * log n * 2О (лог * п)) време.
Аз не мисля, че всеки алгоритъм на умножение може да отнеме по-малко или дори да е равно на O (n). Това просто не е възможно.
2 за отговор № 2
Обърнете внимание на Алгоритъм на Карацуба, Това включва стъпка за рекурсиране, която лесно можете да моделирате с разделяне и завладяване.