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

Требования к алгоритмической среде выполнения для общих математических процедур Графики функций, обычно используемых при анализе алгоритмов, с указанием числа операций $N\; \{\backslash \; displaystyle\; N\}$в зависимости от размера ввода $n\; \{\backslash \; displaystyle\; n\}$для каждой функции

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

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

Примечание. Из-за разнообразия алгоритмов умножения $M\; (n)\; \{\backslash \; displaystyle\; M\; (n)\}$ниже обозначает сложность выбранного алгоритма умножения.

• 1 Арифметические функции
• 2 Алгебраические функции
• 3 Специальные функции
  • 3.1 Элементарные функции
  • 3.2 Неэлементарные функции
  • 3.3 Математические константы
• 4 Теория чисел
• 5 Матричная алгебра
• 6 Преобразования
• 7 Примечания
• 8 Ссылки
• 9 Дополнительная литература

Операция	Вход	Выход	Алгоритм	Сложность
Сложение	Два $n\; \{\backslash \; displaystyle\; n\}$-значные числа, $N\; \{\backslash \; displaystyle\; N\}$и $N\; \{\backslash \; displaystyle\; N\}$	Один $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$-цифровой номер	Добавление в учебник с переносом	$\Theta \; (n),\; \Theta \; (журнал\; \; (N))\; \{\backslash \; displaystyle\; \backslash \; Theta\; (n),\; \backslash \; Theta\; (\backslash \; log\; (N))\}$
Вычитание	Два $n\; \{\backslash \; displaystyle\; n\}$-значные числа, $N\; \{\backslash \; displaystyle\; N\}$и $N\; \{\backslash \; displaystyle\; N\}$	One $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$-цифровое число	Вычитание из учебника с заимствованием	$\Theta \; (n),\; \Theta \; (log\; \; (N))\; \{\backslash \; displaystyle\; \backslash \; Theta\; (n),\; \backslash \; Theta\; (\backslash \; log\; (N))\}$
Умножение	Два $n\; \{\backslash \; displaystyle\; n\}$-цифровые числа.	Один $2\; n\; \{\backslash \; displaystyle\; 2n\}$-цифровое число	Учебное длинное умножение	$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$
			Алгоритм Карацубы	$O\; (n\; 1.585)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{1.585\})\}$
			3-way Умножение Тоома – Кука	$O\; (n\; 1.465)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{1.465\})\}$
			$k\; \{\backslash \; displaystyle\; k\}$-way умножение Toom – Cook	$O\; (n\; log\; \; 2\; k\; -\; 1\; log\; \; k)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{\backslash \; frac\; \{\backslash \; log\; 2k-1\}\; \{\backslash \; log\; k\}\})\}$
			Смешанный уровень Тоома – Кука (Knuth 4.3.3-T)	$O\; (n\; 2\; 2\; log\; \; n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash ,\; 2\; ^\; \{\backslash \; sqrt\; \{2\; \backslash \; log\; n\}\}\; \backslash ,\; \backslash \; log\; n)\}$
			алгоритм Шёнхаге – Штрассена	$O\; (n\; log\; \; n\; log\; \; log\; \; n)\; \{\; \backslash \; displaystyle\; O\; (n\; \backslash \; log\; n\; \backslash \; log\; \backslash \; log\; n)\}$
			алгоритм Фюрера	$O\; (n\; log\; \; n\; 2\; 2\; log\; \ast \; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n\; \backslash ,\; 2\; ^\; \{\; 2\; \backslash \; log\; ^\; \{*\}\; n\})\}$
			алгоритм Харви-Хувена	$O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$
Division	T wo $n\; \{\backslash \; displaystyle\; n\}$-цифровые числа	Одна $n\; \{\backslash \; displaystyle\; n\}$-цифровое число	Полностное деление учебника	$О\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$
			Дивизион Бурникеля-Циглера «разделяй и властвуй»	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (\; M\; (n)\; \backslash \; log\; n)\}$
			деление Ньютона – Рафсона	$O\; (M\; (n))\; \{\backslash \; displaystyle\; O\; (M\; (n))\}$
Квадратный корень	One $n\; \{\backslash \; displaystyle\; n\}$-значное число	Одно $n\; \{\backslash \; displaystyle\; n\}$-цифровое число	метод Ньютона	$O\; (M\; (n))\; \{\backslash \; displaystyle\; O\; (M\; (n))\}$
Модульное возведение в степень	Два $n\; \{\backslash \; displaystyle\; n\}$-цифровых целых чисел и $k\; \{\backslash \; displaystyle\; k\}$-битный показатель степени	Один $n\; \{\backslash \; displaystyle\; n\}$-значное целое число	Повторное умножение и уменьшение	$О\; (M\; (n)\; 2\; K)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash ,\; 2\; ^\; \{k\})\}$
			Возведение в степень возведением в квадрат	$O\; (M\; (n)\; k)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash ,\; k)\}$
			Возведение в степень с редукцией Монтгомери	$O\; (M\; (n)\; k)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash ,\; k)\}$

Операция	Вход	Выход	Алгоритм	Сложность
Полином оценка	Один полином степени $n\; \{\backslash \; displaystyle\; n\}$с коэффициентами фиксированного размера	Одно число фиксированного размера	Прямая оценка	$\Theta \; (n)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (n)\}$
			Метод Хорнера	$\Theta \; (n)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (n)\}$
Полиномиальный НОД (более $Z\; [x]\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; [x]\}$или $F\; [x]\; \{\backslash \; displaystyle\; F\; [x]\}$)	Два полинома степени $n\; \{\backslash \; displaystyle\; n\}$с целочисленными коэффициентами фиксированного размера	Один многочлен степени не выше $n\; \{\backslash \; displaystyle\; n\}$	алгоритм Евклида	$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$
			Быстрый алгоритм Евклида (Lehmer)	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$

Многие методы в этом разделе даны в Borwein Borwein.

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

элементарные функции построены путем составления арифметических операций, экспоненциальная функция ($exp\; \{\backslash \; displaystyle\; \backslash \; exp\}$), натуральный логарифм ($log\; \{\backslash \; displaystyle\; \backslash \; log\}$), тригонометрические функции ($sin,\; cos\; \{\backslash \; displaystyle\; \backslash \; sin,\; \backslash \; cos\}$) и их обратные. Сложность элементарной функции эквивалентна сложности ее обратной, поскольку все элементарные функции аналитические и, следовательно, обратимы с помощью метода Ньютона. В частности, если $exp\; \{\backslash \; displaystyle\; \backslash \; exp\}$или $log\; \{\backslash \; displaystyle\; \backslash \; log\}$в сложном домене может быть вычислено с некоторой сложностью, тогда эта сложность достижима для всех остальных элементарных функций.

Ниже размер $n\; \{\backslash \; displaystyle\; n\}$относится к числу цифр точности, с которой функция должна оцениваться.

Алгоритм	Применимость	Сложность
Ряд Тейлора ; сокращение повторных аргументов (например, $exp\; \; (2\; x)\; =\; [exp\; \; (x)]\; 2\; \{\backslash \; displaystyle\; \backslash \; exp\; (2x)\; =\; [\backslash \; exp\; (x)]\; ^\; \{2\}\}$) и прямое суммирование	$exp,\; log,\; sin,\; cos,\; arctan\; \{\backslash \; displaystyle\; \backslash \; exp,\; \backslash \; log,\; \backslash \; sin,\; \backslash \; cos,\; \backslash \; arctan\}$	$O\; (M\; (n)\; n\; 1/2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; n\; ^\; \{1/2\})\}$
ряд Тейлора; Ускорение на основе БПФ	$exp,\; log,\; sin,\; cos,\; arctan\; \{\backslash \; displaystyle\; \backslash \; exp,\; \backslash \; log,\; \backslash \; sin,\; \backslash \; cos,\; \backslash \; arctan\}$	$O\; (M\; (n)\; n\; 1/3\; (журнал\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; n\; ^\; \{1/3\}\; (\backslash \; log\; n)\; ^\; \{2\})\}$
ряд Тейлора; двоичное разбиение +	$exp,\; log,\; sin,\; cos,\; arctan\; \{\backslash \; displaystyle\; \backslash \; exp,\; \backslash \; log,\; \backslash \; sin,\; \backslash \; cos,\; \backslash \; arctan\}$	$O\; (M\; (n)\; (log\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; (\backslash \; log\; n)\; ^\; \{2\})\}$
Среднее арифметико-геометрическое итерация	$exp,\; log,\; sin,\; cos,\; arctan\; \{\backslash \; displaystyle\; \backslash \; exp,\; \backslash \; log,\; \backslash \; sin,\; \backslash \; cos,\; \backslash \; arctan\}$	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$

Неизвестно, $O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$- оптимальная сложность для элементарных функций. Самая известная нижняя граница - это тривиальная граница $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\}$ $(M\; (n))\; \{\backslash \; displaystyle\; (M\; (n))\}$.

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

Функция	Вход	Алгоритм	Сложность
Гамма-функция	$n\; \{\backslash \; displaystyle\; n\}$-цифровое число	Последовательная аппроксимация неполной гамма-функции	$O\; (M\; (n)\; n\; 1/2\; (log\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; n\; ^\; \{1/2\}\; (\backslash \; log\; n)\; ^\; \{2\})\}$
	Фиксированное рациональное число	Гипергеометрический ряд	$O\; (M\; (n)\; (log\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; (\backslash \; log\; n)\; ^\; \{2\})\}$
	$m\; /\; 24\; \{\backslash \; displaystyle\; m\; /\; 24\}$для $m\; \{\backslash \; displaystyle\; m\}$целое число.	Среднее арифметико-геометрическое итерация	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
Гипергеометрическая функция $p\; F\; q\; \{\backslash \; displaystyle\; \{\}\; \_\; \{p\}\; \backslash !\; F\_\; \{q\}\}$	$n\; \{\backslash \; displaystyle\; n\}$-цифровое число	(как описано в Borwein Borwein)	$О\; (M\; (n)\; n\; 1/2\; (журнал\; \; n)\; 2)\; \{\backslash \; Displaystyle\; O\; (M\; (n)\; n\; ^\; \{1/2\}\; (\backslash \; log\; n)\; ^\; \{2\})\}$
	Фиксированное рациональное число	Гипергеометрический ряд	$O\; (M\; (n)\; (log\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; (\backslash \; log\; n)\; ^\; \{2\})\}$

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

В этой таблице указана сложность вычисления приближений к заданным константам для $n\; \{\backslash \; displaystyle\; n\}$правильных цифр.

Константа	Алгоритм	Сложность
Золотое сечение, $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$	Метод Ньютона	$O\; (M\; (n))\; \{\backslash \; displaystyle\; O\; (M\; (n))\}$
квадратный корень из 2, $2\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{2\}\}\}$	метод Ньютона	$O\; (M\; (n))\; \{\backslash \; displaystyle\; O\; (M\; (n))\}$
число Эйлера, $e\; \{\backslash \; displaystyle\; e\}$	двоичное расщепление ряда Тейлора для экспоненциальной функции	$O\; (M\; (n)\; журнал\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
	Обращение натурального логарифма Ньютона	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
Pi, $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$	Двоичное разбиение ряда arctan в формуле Мачина	$O\; (M\; (n)\; (log\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; (\backslash \; log\; n)\; ^\; \{2\})\}$
	алгоритм Гаусса – Лежандра	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (\; n)\; \backslash \; log\; n)\}$
постоянная Эйлера, $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$	метод Суини (аппроксимация в терминах экспоненциального интеграла )	$O\; (M\; (n)\; (журнал\; \; n)\; 2)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; (\backslash \; log\; n)\; ^\; \{2\})\}$

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

Операция	Вход	Выход	Алгоритм	Сложность
Наибольший общий делитель	Два $n\; \{\backslash \; displaystyle\; n\}$-цифровые целые числа	Одно целое число, состоящее не более чем из $n\; \{\backslash \; displaystyle\; n\}$цифр	алгоритм Евклида	$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$
			Алгоритм двоичного GCD	$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$
			влево / вправо k- арный алгоритм двоичного НОД	$O\; (n\; 2\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\}\; \backslash \; log\; n)\}$
				$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (\; n)\; \backslash \; log\; n)\}$
				$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
символ Якоби	Два $n\; \{\backslash \; displaystyle\; n\}$-цифровые целые	$0\; \{\backslash \; displaystyle\; 0\}$, $-\; 1\; \{\backslash \; displaystyle\; -1\}$или $1\; \{\backslash \; displaystyle\; 1\}$	Управляемый Шёнхаге алгоритм евклидова спуска	$O\; (M\; (\; n)\; журнал\; \; N)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
			алгоритм Стеле – Циммермана	$O\; (M\; (n)\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (M\; (n)\; \backslash \; log\; n)\}$
Факториал	Положительное целое число меньше $m\; \{\backslash \; displaystyle\; m\}$	One $O\; (m\; log\; \; m)\; \{\backslash \; displaystyle\; O\; (m\; \backslash \; log\; m)\}$-цифровое целое число	Умножение снизу вверх	$O\; (M\; (m\; 2)\; log\; \; m)\; \{\backslash \; displaystyle\; O\; (M\; (m\; ^\; \{2\})\; \backslash \; log\; m)\; \}$
			Двоичное разбиение	$O\; (M\; (m\; log\; \; m)\; log\; \; m)\; \{\backslash \; displaystyle\; O\; (M\; (m\; \backslash \; log\; m)\; \backslash \; log\; m)\}$
			Возведение в степень простых множителей $m\; \{\backslash \; displaystyle\; m\}$	$O\; (M\; (m\; log\; \; m)\; log\; \; log\; \; m)\; \{\backslash \; displaystyle\; O\; (M\; (m\; \backslash \; log\; m)\; \backslash \; log\; \backslash \; log\; m)\}$,. $O\; (M\; (m\; log\; \; m))\; \{\backslash \; displaystyle\; O\; (M\; (m\; \backslash \; log\; m))\}$
Тест на простоту	A $n\; \{\backslash \; displaystyle\; n\}$-цифровое целое число	Верно или нет	Тест простоты AKS	$O\; (n\; 6)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{6\})\}$или $O\; (n\; 6\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{6+\; \backslash \; varepsilon\})\}$,. $O\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$, предполагая гипотезу Агравала
			Доказательство простоты эллиптической кривой	$O\; (n\; 4\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{4+\; \backslash \; varepsilon\})\}$эвристически
			тест простоты Baillie-PSW	$О\; (n\; 2\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2+\; \backslash \; varepsilon\})\}$
			Тест простоты Миллера – Рабина	$O\; (kn\; 2\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (kn\; ^\; \{2+\; \backslash \; varepsilon\})\}$
			Тест простоты Соловея – Штрассена	$O\; (kn\; 2\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (kn\; ^\; \{2+\; \backslash \; varepsilon\})\}$
Целочисленная факторизация	A $b\; \{\backslash \; displaystyle\; b\}$-битовое целое число	Набор множителей	Сито общего числового поля	$O\; ((1\; +\; \epsilon )\; b)\; \{\backslash \; displaystyle\; O\; ((1+\; \backslash \; varepsilon)\; ^\; \{b\})\}$
			алгоритм Шора	$O\; (b\; 3)\; \{\backslash \; displaystyle\; O\; (b\; ^\; \{3\})\}$на квантовом компьютере

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

Операция	Вход	Выход	Алгоритм	Сложность
Умножение матриц	Две $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрицы	One $n\; \times \; n\; \{\; \backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица	Умножение матриц учебника	$O\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$
			алгоритм Штрассена	$O\; (\; n\; 2.807)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.807\})\}$
			алгоритм Копперсмита – Винограда	$O\; (n\; 2.376)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.376\})\}$
			Оптимизированные алгоритмы, подобные CW	$O\; (n\; 2.373)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.373\})\}$
Умножение матрицы	One $n\; \times \; m\; \{\backslash \; displaystyle\; n\; \backslash \; times\; m\}$матрица одна $m\; \times \; p\; \{\backslash \; displaystyle\; m\; \backslash \; times\; p\}$матрица	One $n\; \times \; p\; \{\backslash \; displaystyle\; n\; \backslash \; times\; p\}$матрица	Умножение матриц в учебнике	$O\; (nmp)\; \{\backslash \; displaystyle\; O\; (nmp)\}$
Умножение матриц	One $n\; \times \; \lceil \; n\; \rceil \; \{\backslash \; displaystyle\; n\; \backslash \; times\; \backslash \; lceil\; n\; \backslash \; rceil\}$matrix one $\lceil \; n\; \rceil \; \times \; n\; \{\backslash \; displaystyle\; \backslash \; lceil\; n\; \backslash \; rceil\; \backslash \; times\; n\}$matrix	Один $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$matrix	Алгоритмы, указанные в	$O\; (n\; \omega \; (k)\; +\; ϵ)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{\backslash \; omega\; (k)\; +\; \backslash \; epsilon\})\}$, где верхние границы для $\omega \; (k)\; \{\backslash \; displaystyle\; \backslash \; omega\; (k)\}$даны в
Инверсия матриц	Один $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица	One $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица	исключение Гаусса – Джордана	$O\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$
			алгоритм Штрассена	$O\; (n\; 2.807)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.807\})\}$
			Алгоритм Копперсмита – Винограда	$O\; (n\; 2.376)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.376\})\}$
			Оптимизированные алгоритмы, подобные CW	$O\; (n\; 2.373)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.373\})\}$
Разложение по сингулярным числам	Один $m\; \times \; n\; \{\backslash \; displaystyle\; m\; \backslash \; times\; n\}$матрица	Одна матрица $m\; \times \; m\; \{\backslash \; displaystyle\; m\; \backslash \; times\; m\}$,. одна $m\; \times \; n\; \{\backslash \; displaystyle\; m\; \backslash \; times\; n\}$матрица,. один $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица ix	Бидиагонализация и алгоритм QR	$O\; (mn\; 2\; +\; m\; 2\; n)\; \{\backslash \; displaystyle\; O\; (mn\; ^\; \{2\}\; +\; m\; ^\; \{2\}\; n)\}$. ($m\; \ge \; n\; \{\backslash \; displaystyle\; m\; \backslash \; geq\; n\}$)
		Одна $m\; \times \; n\; \{\backslash \; displaystyle\; m\; \backslash \; times\; n\}$матрица,. одна $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица. одна $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица	Бидиагонализация и QR-алгоритм	$O\; (mn\; 2)\; \{\backslash \; displaystyle\; O\; (mn\; ^\; \{2\})\}$. ($m\; \ge \; n\; \{\backslash \; displaystyle\; m\; \backslash \; geq\; n\}$)
Определитель	One $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$матрица	Одно число	расширение Лапласа	$O\; (n!)\; \{\backslash \; displaystyle\; O\; (n!)\}$
			Алгоритм без деления	$O\; (n\; 4)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{4\})\}$
			LU-разложение	$O\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$
			алгоритм Барейсса	$O\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$
			Быстрое умножение матриц	$O\; (n\; 2.373)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2.373\})\}$
Обратная подстановка	Треугольная матрица	$n\; \{\backslash \; displaystyle\; n\}$решения	Обратная подстановка	$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$

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

^*Из-за возможности поблочного обращения матрицы, где инверсия матрица $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$требует инверсии двух матриц половинного размера и шести умножений между двумя матрицами половинного размера, а так как умножение матриц имеет нижнюю границу $Ом\; \{\backslash \; дис\; playstyle\; \backslash \; Omega\}$ ($n\; 2\; log\; \; n\; \{\backslash \; displaystyle\; n\; ^\; \{2\}\; \backslash \; log\; n\}$) операций, можно показать, что алгоритм разделяй и властвуй, который использует поблочное обращение для инвертирования матрицы, выполняется с той же временной сложностью, что и алгоритм умножения матриц, который используется внутри.

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

Операция	Вход	Выход	Алгоритм	Сложность
Дискретное преобразование Фурье	Конечная последовательность данных размера $n\; \{\backslash \; displaystyle\; n\}$	Набор комплексных чисел	Быстрое преобразование Фурье	$O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$

• Брент, Ричард П. ; Циммерманн, Пол (2010). Современная компьютерная арифметика. Издательство Кембриджского университета. ISBN 978-0-521-19469-3.
• Кнут, Дональд Эрвин (1997). Искусство программирования. Том 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89684-8.