WikiDer > Вычислительная сложность математических операций

Computational complexity of mathematical operations
Графики функций, обычно используемых при анализе алгоритмов, с указанием количества операций по сравнению с размером ввода для каждой функции

В следующих таблицах перечислены вычислительная сложность различных алгоритмы для общего математические операции.

Здесь под сложностью понимается временная сложность выполнения вычислений на многолента машина Тьюринга.[1] Видеть нотация большой O для объяснения используемых обозначений.

Примечание: из-за разнообразия алгоритмов умножения ниже обозначает сложность выбранного алгоритма умножения.

Арифметические функции

ОперацияВходВыходАлгоритмСложность
ДобавлениеДва -значные числа, и Один -цифровой номерДополнение к учебнику с переноской
ВычитаниеДва -значные числа, и Один -цифровой номерВычитание из учебника с заимствованием
УмножениеДва -цифровые числа
Один -цифровой номерУчебник длинного умножения
Алгоритм Карацубы
3-ходовой Умножение Тоома – Кука
умножение Тоома – Кука
Смешанный уровень Тоома – Кука (Knuth 4.3.3-T)[2]
Алгоритм Шёнхаге – Штрассена
Алгоритм Фюрера[3]
Алгоритм Харви-Хувена[4] [5]
РазделениеДва -цифровые числаОдин -цифровой номерУчебник с длинным делением
Burnikel-Ziegler Дивизион "разделяй и властвуй" [6]
Деление Ньютона – Рафсона
Квадратный кореньОдин -цифровой номерОдин -цифровой номерМетод Ньютона
Модульное возведение в степеньДва -цифровые целые числа и -битовая экспонентаОдин -цифровое целое числоПовторное умножение и сокращение
Возведение в степень возведением в квадрат
Возведение в степень с Редукция Монтгомери

Алгебраические функции

ОперацияВходВыходАлгоритмСложность
Полиномиальный оценкаОдин многочлен степени с коэффициентами фиксированного размераОдно число фиксированного размераПрямая оценка
Метод Хорнера
Полиномиальный НОД (более или же )Два полинома степени с целочисленными коэффициентами фиксированного размераОдин многочлен степени не выше Евклидов алгоритм
Быстрый алгоритм Евклида (Лемера)[7]

Специальные функции

Многие методы в этом разделе приведены в Borwein & Borwein.[8]

Элементарные функции

В элементарные функции построены путем составления арифметических операций, экспоненциальная функция (), натуральный логарифм (), тригонометрические функции () и их обратные. Сложность элементарной функции эквивалентна сложности ее обратной, поскольку все элементарные функции аналитический и, следовательно, обратимы с помощью метода Ньютона. В частности, если или же в комплексной области может быть вычислена с некоторой сложностью, тогда эта сложность достижима для всех других элементарных функций.

Ниже размер относится к количеству цифр точности, с которым функция должна быть оценена.

АлгоритмПрименимостьСложность
Серия Тейлор; сокращение повторных аргументов (например, ) и прямое суммирование
Серия Тейлора; БПФ-основное ускорение
Серия Тейлора; двоичное расщепление + битовый алгоритм[9]
Среднее арифметико-геометрическое итерация[10]

Неизвестно, были ли оптимальная сложность для элементарных функций. Самая известная нижняя оценка - тривиальная оценка .

Неэлементарные функции

ФункцияВходАлгоритмСложность
Гамма-функция-цифровой номерАппроксимация рядами неполная гамма-функция
Фиксированное рациональное числоГипергеометрический ряд
, за целое число.Среднее арифметико-геометрическое итерация
Гипергеометрическая функция -цифровой номер(Как описано в Borwein & Borwein)
Фиксированное рациональное числоГипергеометрический ряд

Математические константы

В этой таблице указана сложность вычисления приближений заданных констант к правильные цифры.

ПостоянныйАлгоритмСложность
Золотое сечение, Метод Ньютона
Корень квадратный из 2, Метод Ньютона
Число Эйлера, Двоичное расщепление ряда Тейлора для экспоненциальной функции
Обращение Ньютона натурального логарифма
число Пи, Двоичное расщепление арктанового ряда в Формула Мачина[11]
Алгоритм Гаусса – Лежандра[11]
Постоянная Эйлера, Метод Суини (приближение в терминах экспоненциальный интеграл)

Теория чисел

Алгоритмы для теоретическое число расчеты изучаются в вычислительная теория чисел.

ОперацияВходВыходАлгоритмСложность
Наибольший общий делительДва -значные целые числаОдно целое число с не более чем цифрыЕвклидов алгоритм
Бинарный алгоритм GCD
Лево право k-арный двоичный алгоритм НОД[12]
Алгоритм Стеле – Циммермана[13]
Управляемый Шёнхаге алгоритм евклидова спуска[14]
Символ ЯкобиДва -значные целые числа, или же Управляемый Шёнхаге алгоритм евклидова спуска[15]
Алгоритм Стеле – Циммермана[16]
ФакториалПоложительное целое число меньше Один -цифровое целое числоУмножение снизу вверх
Двоичное расщепление
Возведение в степень простых факторов ,[17]
[1]
Тест на первичностьА -цифровое целое числоПравда или ложьТест на простоту AKS[18] [19] или же [20][21],
, предполагая Гипотеза Агравала
Доказательство простоты эллиптической кривой эвристически[22]
Тест на простоту Baillie-PSW[23][24]
Тест на простоту Миллера – Рабина[25]
Тест на простоту Соловея – Штрассена[25]
Целочисленная факторизацияА -битовое целое числоНабор факторовОбщее числовое поле сито[nb 1]
Алгоритм Шора, на квантовый компьютер

Матричная алгебра

Следующие цифры сложности предполагают, что арифметика с отдельными элементами имеет сложность О(1), как и в случае с фиксированной точностью арифметика с плавающей запятой или операции на конечное поле.

ОперацияВходВыходАлгоритмСложность
Умножение матрицДва матрицыОдин матрицаУмножение матриц учебника
Алгоритм Штрассена
Алгоритм Копперсмита – Винограда
Оптимизированные CW-подобные алгоритмы[26][27][28]
Умножение матрицОдин матрица и

один матрица

Один матрицаУмножение матриц учебника
Умножение матрицОдин матрица и

один матрица, для некоторых

Один матрицаАлгоритмы приведены в [29], где оценки сверху на даны в [29]
Обращение матрицы*Один матрицаОдин матрицаИсключение Гаусса – Жордана
Алгоритм Штрассена
Алгоритм Копперсмита – Винограда
Оптимизированные CW-подобные алгоритмы
Разложение по сингулярным числамОдин матрицаОдин матрица
один матрица, &
один матрица
Бидиагонализация и QR-алгоритм
()
Один матрица
один матрица, &
один матрица
Бидиагонализация и QR-алгоритм
()
ДетерминантОдин матрицаОдин номерРазложение лапласа
Алгоритм без деления[30]
LU разложение
Алгоритм Барейса
Быстрое матричное умножение[31]
Обратная подстановкаТреугольная матрица решенияОбратная подстановка[32]

В 2005 году, Генри Кон, Роберт Клейнберг, Балаж Сегеди, и Крис Уманс показал, что из любой из двух гипотез следует, что показатель умножения матриц равен 2.[33]

^* Из-за возможности поблочное инвертирование матрицы, где инверсия Матрица требует инверсии двух матриц половинного размера и шести умножений между двумя матрицами половинного размера, а поскольку умножение матриц имеет нижнюю границу () операции,[34] можно показать, что разделяй и властвуй алгоритм который использует поблочное обращение для инвертирования матрицы, выполняется с той же временной сложностью, что и алгоритм умножения матриц, который используется внутри компании.[35]

Трансформирует

Алгоритмы вычислений трансформирует функций (особенно интегральные преобразования) широко используются во всех областях математики, в частности анализ и обработка сигналов.

ОперацияВходВыходАлгоритмСложность
Дискретное преобразование ФурьеКонечная последовательность данных размера Набор комплексных чиселБыстрое преобразование Фурье

Примечания

  1. ^ Эта форма субэкспоненциального времени действительна для всех . Более точная форма сложности может быть дана как

Рекомендации

  1. ^ а б А. Шёнхаге, A.F.W. Гротефельд, Э. Веттер: Быстрые алгоритмы - реализация многоленточной машины Тьюринга, BI Wissenschafts-Verlag, Мангейм, 1994 г.
  2. ^ Д. Кнут. Искусство программирования, Том 2. Третье издание, Addison-Wesley 1997.
  3. ^ Мартин Фюрер. Более быстрое целочисленное умножение [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf В архиве 2013-04-25 в Wayback Machine. Материалы 39-й ежегодной Симпозиум ACM по теории вычислений, Сан-Диего, Калифорния, США, 11–13 июня 2007 г., стр. 55–67.
  4. ^ Дэвид Харви, Йорис ван дер Хувен Целочисленное умножение за время O (n log n). (2019).
  5. ^ Эрика Кларрайх. 2019. Умножение достигает предела скорости. Commun. ACM 63, 1 (декабрь 2019 г.), 11–13. Дои:10.1145/3371387
  6. ^ Кристоф Бурникель и Иоахим Циглер Быстрое рекурсивное деление Im Stadtwald, D-Saarbrucken 1998.
  7. ^ http://planetmath.org/fasteuclideanalgorithm
  8. ^ J. Borwein и P. Borwein. Пи и AGM: исследование аналитической теории чисел и вычислительной сложности. Джон Вили 1987.
  9. ^ Давид и Григорий Чудновские. Приближения и комплексное умножение по Рамануджану. Рамануджан снова, Academic Press, 1988, стр. 375–472.
  10. ^ Ричард П. Брент, Методы определения нуля с высокой точностью и сложность вычисления элементарных функций, в: Аналитическая вычислительная сложность (изд. Дж. Ф. Трауб), Academic Press, Нью-Йорк, 1975, 151–176.
  11. ^ а б Ричард П. Брент (2020), Братья Борвейн, Пи и Общее собрание акционеров, Springer Proceedings по математике и статистике, 313, arXiv:1802.07558, Дои:10.1007/978-3-030-36568-4, ISBN 978-3-030-36567-7
  12. ^ Дж. Соренсон. (1994). «Два быстрых алгоритма НОД». Журнал алгоритмов. 16 (1): 110–144. Дои:10.1006 / jagm.1994.1006.
  13. ^ Р. Крэндалл и К. Померанс. Простые числа - вычислительная перспектива. Второе издание, Springer 2005.
  14. ^ Мёллер Н. (2008). «Об алгоритме Шёнхаге и вычислении субквадратичного целочисленного НОД» (PDF). Математика вычислений. 77 (261): 589–607. Bibcode:2008MaCom..77..589M. Дои:10.1090 / S0025-5718-07-02017-0.
  15. ^ Бернштейн Д. Дж. «Более быстрые алгоритмы для поиска целых чисел, не являющихся квадратами по модулю наихудшего случая».
  16. ^ Ричард П. Брент; Пол Циммерманн (2010). "An алгоритм для символа Якоби ». arXiv:1004.2091 [cs.DS].
  17. ^ Борвейн, П. (1985). «О сложности вычисления факториалов». Журнал алгоритмов. 6 (3): 376–380. Дои:10.1016/0196-6774(85)90006-9.
  18. ^ Х. В. Ленстра-младший и Карл Померанс "Проверка на простоту с гауссовыми периодами", предварительная версия от 20 июля 2005 г.
  19. ^ Х. В. Ленстра мл. и Карл Померанс "Проверка на простоту с гауссовыми периодами В архиве 2012-02-25 в Wayback Machine", версия от 12 апреля 2011 г.
  20. ^ Тао, Теренс (2010). «1.11 Тест простоты AKS». Эпсилон комнаты, II: страницы третьего курса математического блога. Аспирантура по математике. 117. Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. Дои:10,1090 / г / м2 / 117. ISBN 978-0-8218-5280-4. МИСТЕР 2780010.
  21. ^ Ленстра-младший, Х.В.; Померанс, Карл (11 декабря 2016 г.). «Проверка примитивности с гауссовыми периодами» (PDF). Цитировать журнал требует | журнал = (помощь)
  22. ^ Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений. 76 (257): 493–505. arXiv:математика / 0502097. Bibcode:2007MaCom..76..493M. Дои:10.1090 / S0025-5718-06-01890-4. МИСТЕР 2261033. S2CID 133193.
  23. ^ Карл Померанс; Джон Л. Селфридж; Сэмюэл С. Вагстафф-мл. (Июль 1980 г.). «Псевдопреступности до 25 · 109" (PDF). Математика вычислений. 35 (151): 1003–1026. Дои:10.1090 / S0025-5718-1980-0572872-7. JSTOR 2006210.
  24. ^ Роберт Бэйли; Сэмюэл С. Вагстафф-мл. (Октябрь 1980 г.). "Лукас Псевдопримес" (PDF). Математика вычислений. 35 (152): 1391–1417. Дои:10.1090 / S0025-5718-1980-0583518-6. JSTOR 2006406. МИСТЕР 0583518.
  25. ^ а б Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика. 12 (1): 97–108. Дои:10.1016/0304-3975(80)90007-9. МИСТЕР 0582244.
  26. ^ Дэви, A.M .; Стотерс, А.Дж. (2013), «Улучшенная оценка сложности умножения матриц», Труды Королевского общества Эдинбурга, 143A (2): 351–370, Дои:10.1017 / S0308210511001648
  27. ^ Василевска Уильямс, Вирджиния (2011), Преодоление барьера медников-виноград (PDF)
  28. ^ Ле Галл, Франсуа (2014), «Степени тензоров и быстрое матричное умножение», Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014), arXiv:1401.7714, Bibcode:2014arXiv1401.7714L
  29. ^ а б Ле Галль, Франсуа; Уррутия, Флорен (2018). «Улучшенное умножение прямоугольной матрицы с использованием степеней тензора Медника-Винограда». В Czumaj, Артур (ред.). Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики (SIAM). Дои:10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID 33396059.
  30. ^ http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf
  31. ^ Ахо, Альфред В.; Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов, Аддисон-Уэсли, теорема 6.6, с. 241
  32. ^ Дж. Б. Фрали и Р. А. Борегар, "Линейная алгебра", издательство Addison-Wesley Publishing Company, 1987, стр. 95.
  33. ^ Генри Кон, Роберт Кляйнберг, Балаш Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv:math.GR/0511460. Материалы 46-го ежегодного симпозиума по основам информатики, 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.
  34. ^ Ран Раз. О сложности матричного произведения. В материалах тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM Press, 2002. Дои:10.1145/509907.509932.
  35. ^ T.H. Кормен, К.Е. Лейзерсон, Р.Л. Ривест, К. Штайн, Введение в алгоритмы, 3-е изд., MIT Press, Кембридж, Массачусетс, 2009, § 28.2.

дальнейшее чтение