В школе нас учили, как умножать числа в столбик. Асимптотическая сложность для такого "алгоритма" – O(n^2). Это значит, что на умножение двух чисел, состоящих из 5 цифр, нам надо выполнить 5^2 = 25 операций. Есть другой способ – метод быстрого умножения Карацубы. Он имеет сложность O(n^1.58). Например, вы решили перемножить два числа состоящих из 1000 цифр. Если вы умножаете в столбик, вы совершите 1млн операций. Используя метод К., вы сделаете около 50 тысяч операций – т. е. умножите в 20 раз быстрее.
Комментариев нет:
Отправить комментарий