Обзор: Самый быстрый известный алгоритм умножения
Самый быстрый известный алгоритм умножения целых чисел даёт преимущество только на абсурдно больших числах.В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как .
Алгоритм Харви — ван дер Хувена — алгоритм умножения двух -битных целых чисел с временной сложностью в модели многоленточной машины Тьюринга. Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.
Теги: Временная сложность алгоритма Алгоритм Харви — ван дер Хувена Самый быстрый известный алгоритм умножения целых чисел даёт преимущество больших