Английская Википедия:Computational complexity of mathematical operations

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations <math>N</math> versus input size <math>n</math> for each function

The following tables list the computational complexity of various algorithms for common mathematical operations.

Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.^[1] See big O notation for an explanation of the notation used.

Note: Due to the variety of multiplication algorithms, <math>M(n)</math> below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functions

This table lists the complexity of mathematical operations on integers.

Operation	Input	Output	Algorithm	Complexity
Addition	Two <math>n</math>-digit numbers	One <math>n+1</math>-digit number	Schoolbook addition with carry	<math>\Theta(n)</math>
Subtraction	Two <math>n</math>-digit numbers	One <math>n+1</math>-digit number	Schoolbook subtraction with borrow	<math>\Theta(n)</math>
Multiplication	Two <math>n</math>-digit numbers	One <math>2n</math>-digit number	Schoolbook long multiplication	<math>O\mathord\left(n^{2}\right)</math>
			Karatsuba algorithm	<math>O\mathord\left(n^{1.585}\right)</math>
			3-way Toom–Cook multiplication	<math>O\mathord\left(n^{1.465}\right)</math>
			<math>k</math>-way Toom–Cook multiplication	<math>O\mathord\left(n^{\frac{\log(2k - 1)}{\log k}}\right)</math>
			Mixed-level Toom–Cook (Knuth 4.3.3-T)^[2]	<math>O\mathord\left(n \, 2^{\sqrt{2 \log n}} \, \log n\right)</math>
			Schönhage–Strassen algorithm	<math>O\mathord\left(n \log n \log \log n\right)</math>
			Harvey-Hoeven algorithm^[3]^[4]	<math>O(n \log n)</math>
Division	Two <math>n</math>-digit numbers	One <math>n</math>-digit number	Schoolbook long division	<math>O\mathord\left(n^{2}\right)</math>
			Burnikel–Ziegler Divide-and-Conquer Division^[5]	<math>O(M(n) \log n)</math>
			Newton–Raphson division	<math>O(M(n))</math>
Square root	One <math>n</math>-digit number	One <math>n</math>-digit number	Newton's method	<math>O(M(n))</math>
Modular exponentiation	Two <math>n</math>-digit integers and a <math>k</math>-bit exponent	One <math>n</math>-digit integer	Repeated multiplication and reduction	<math>O\mathord\left(M(n) \, 2^{k}\right)</math>
			Exponentiation by squaring	<math>O(M(n) \, k)</math>
			Exponentiation with Montgomery reduction	<math>O(M(n) \, k)</math>

On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two Шаблон:Mvar-bit numbers in time O(n).^[6]

Algebraic functions

Here we consider operations over polynomials and Шаблон:Mvar denotes their degree; for the coefficients we use a unit-cost model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers.

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree <math>n</math> with integer coefficients	One number	Direct evaluation	<math>\Theta(n)</math>
Polynomial evaluation		One number	Horner's method	<math>\Theta(n)</math>
Polynomial gcd (over <math>\mathbb{Z}[x]</math> or <math>F[x]</math>)	Two polynomials of degree <math>n</math> with integer coefficients	One polynomial of degree at most <math>n</math>	Euclidean algorithm	<math>O\mathord\left(n^{2}\right)</math>
		One polynomial of degree at most <math>n</math>	Fast Euclidean algorithm (Lehmer)Шаблон:Citation needed	<math>O(M(n) \log n)</math>

Special functions

Many of the methods in this section are given in Borwein & Borwein.^[7]

Elementary functions

The elementary functions are constructed by composing arithmetic operations, the exponential function (<math>\exp</math>), the natural logarithm (<math>\log</math>), trigonometric functions (<math>\sin, \cos</math>), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic and hence invertible by means of Newton's method. In particular, if either <math>\exp</math> or <math>\log</math> in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.

Below, the size <math>n</math> refers to the number of digits of precision at which the function is to be evaluated.

Algorithm	Applicability	Complexity
Taylor series; repeated argument reduction (e.g. <math>\exp(2x) = [\exp(x)]^2</math>) and direct summation	<math>\exp, \log, \sin, \cos, \arctan</math>	<math>O\mathord\left(M(n) n^{1/2}\right)</math>
Taylor series; FFT-based acceleration	<math>\exp, \log, \sin, \cos, \arctan</math>	<math>O\mathord\left(M(n) n^{1/3} (\log n)^2\right)</math>
Taylor series; binary splitting + bit-burst algorithm^[8]	<math>\exp, \log, \sin, \cos, \arctan</math>	<math>O\mathord\left(M(n) (\log n)^2\right)</math>
Arithmetic–geometric mean iteration^[9]	<math>\exp, \log, \sin, \cos, \arctan</math>	<math>O(M(n) \log n)</math>

It is not known whether <math>O(M(n) \log n)</math> is the optimal complexity for elementary functions. The best known lower bound is the trivial bound Шаблон:Math<math>(M(n))</math>.

Non-elementary functions

Function	Input	Algorithm	Complexity
Gamma function	<math>n</math>-digit number	Series approximation of the incomplete gamma function	<math>O\mathord\left(M(n) n^{1/2} (\log n)^2\right)</math>
	Fixed rational number	Hypergeometric series	<math>O\mathord\left(M(n) (\log n)^2\right)</math>
	<math>m/24</math>, for <math>m</math> integer.	Arithmetic-geometric mean iteration	<math>O(M(n) \log n)</math>
Hypergeometric function <math>{}_p\!F_q</math>	<math>n</math>-digit number	(As described in Borwein & Borwein)	<math>O\mathord\left(M(n) n^{1/2} (\log n)^2\right)</math>
Hypergeometric function <math>{}_p\!F_q</math>	Fixed rational number	Hypergeometric series	<math>O\mathord\left(M(n) (\log n)^2\right)</math>

Mathematical constants

This table gives the complexity of computing approximations to the given constants to <math>n</math> correct digits.

Constant	Algorithm	Complexity
Golden ratio, <math>\phi</math>	Newton's method	<math>O(M(n))</math>
Square root of 2, <math>\sqrt{2}</math>	Newton's method	<math>O(M(n))</math>
Euler's number, <math>e</math>	Binary splitting of the Taylor series for the exponential function	<math>O(M(n) \log n)</math>
Euler's number, <math>e</math>	Newton inversion of the natural logarithm	<math>O(M(n) \log n)</math>
Pi, <math>\pi</math>	Binary splitting of the arctan series in Machin's formula	<math>O\mathord\left(M(n) (\log n)^2\right)</math>^[10]
Pi, <math>\pi</math>	Gauss–Legendre algorithm	<math>O(M(n) \log n)</math>^[10]
Euler's constant, <math>\gamma</math>	Sweeney's method (approximation in terms of the exponential integral)	<math>O\mathord\left(M(n) (\log n)^2\right)</math>

Number theory

Algorithms for number theoretical calculations are studied in computational number theory.

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two <math>n</math>-digit integers	One integer with at most <math>n</math> digits	Euclidean algorithm	<math>O\mathord\left(n^{2}\right)</math>
			Binary GCD algorithm	<math>O\mathord\left(n^2\right)</math>
			Left/right k-ary binary GCD algorithm^[11]	<math>O\mathord\left(\frac{n^{2}}{\log n}\right)</math>
			Stehlé–Zimmermann algorithm^[12]	<math>O(M(n) \log n)</math>
			Schönhage controlled Euclidean descent algorithm^[13]	<math>O(M(n) \log n)</math>
Jacobi symbol	Two <math>n</math>-digit integers	<math>0</math>, <math>-1</math> or <math>1</math>	Schönhage controlled Euclidean descent algorithm^[14]	<math>O(M(n) \log n)</math>
Jacobi symbol	Two <math>n</math>-digit integers	<math>0</math>, <math>-1</math> or <math>1</math>	Stehlé–Zimmermann algorithm^[15]	<math>O(M(n) \log n)</math>
Factorial	A positive integer less than <math>m</math>	One <math>O(m \log m)</math>-digit integer	Bottom-up multiplication	<math>O\mathord\left(M\left(m^2\right) \log m\right)</math>
			Binary splitting	<math>O(M(m \log m) \log m)</math>
			Exponentiation of the prime factors of <math>m</math>	<math>O(M(m \log m) \log \log m)</math>,^[16] <math>O(M(m \log m))</math>^[1]
Primality test	A <math>n</math>-digit integer	True or false	AKS primality test	<math>O\mathord\left(n^{6+o(1)}\right)</math>^[17]^[18] <math>O(n^{3})</math>, assuming Agrawal's conjecture
			Elliptic curve primality proving	<math>O\mathord\left(n^{4+\varepsilon}\right)</math> heuristically^[19]
			Baillie–PSW primality test	<math>O\mathord\left(n^{2+\varepsilon}\right)</math>^[20]^[21]
			Miller–Rabin primality test	<math>O\mathord\left(kn^{2+\varepsilon}\right)</math>^[22]
			Solovay–Strassen primality test	<math>O\mathord\left(kn^{2+\varepsilon}\right)</math>^[22]
Integer factorization	A <math>b</math>-bit input integer	A set of factors	General number field sieve	<math>O\mathord\left((1+\varepsilon)^b\right)</math>^{[nb 1]}
Integer factorization	A <math>b</math>-bit input integer	A set of factors	Shor's algorithm	<math>O(M(b) b)</math>, on a quantum computer

Matrix algebra

Шаблон:Main The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic or operations on a finite field.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two <math>n \times n</math> matrices	One <math>n \times n</math> matrix	Schoolbook matrix multiplication	<math>O(n^{3})</math>
			Strassen algorithm	<math>O\mathord\left(n^{2.807}\right)</math>
			Coppersmith–Winograd algorithm (galactic algorithm)	<math>O\mathord\left(n^{2.376}\right)</math>
			Optimized CW-like algorithms^[23]^[24]^[25]^[26] (galactic algorithms)	<math>O\mathord\left(n^{2.3728596}\right)</math>
Matrix multiplication	One <math>n \times m</math> matrix, and one <math>m \times p</math> matrix	One <math>n \times p</math> matrix	Schoolbook matrix multiplication	<math>O(nmp)</math>
Matrix multiplication	One <math>n \times \left\lceil n^k \right\rceil</math> matrix, and one <math>\left\lceil n^k \right\rceil \times n</math> matrix, for some <math>k \geq 0</math>	One <math>n \times n</math> matrix	Algorithms given in ^[27]	<math>O(n^{\omega(k)+\epsilon})</math>, where upper bounds on <math>\omega(k)</math> are given in ^[27]
Matrix inversion	One <math>n \times n</math> matrix	One <math>n \times n</math> matrix	Gauss–Jordan elimination	<math>O\mathord\left(n^{3}\right)</math>
			Strassen algorithm	<math>O\mathord\left(n^{2.807}\right)</math>
			Coppersmith–Winograd algorithm	<math>O\mathord\left(n^{2.376}\right)</math>
			Optimized CW-like algorithms	<math>O\mathord\left(n^{2.373}\right)</math>
Singular value decomposition	One <math>m \times n</math> matrix	One <math>m \times m</math> matrix, one <math>m \times n</math> matrix, & one <math>n \times n</math> matrix	Bidiagonalization and QR algorithm	<math>O\mathord\left(m^{2}n\right)</math> (<math>m \geq n</math>)
Singular value decomposition	One <math>m \times n</math> matrix	One <math>m\times n</math> matrix, one <math>n \times n</math> matrix, & one <math>n \times n</math> matrix	Bidiagonalization and QR algorithm	<math>O\mathord\left(mn^{2}\right)</math> (<math>m \leq n</math>)
Determinant	One <math>n \times n</math> matrix	One number	Laplace expansion	<math>O(n!)</math>
			Division-free algorithm^[28]	<math>O\mathord\left(n^{4}\right)</math>
			LU decomposition	<math>O(n^{3})</math>
			Bareiss algorithm	<math>O\mathord\left(n^3\right)</math>
			Fast matrix multiplication^[29]	<math>O\mathord\left(n^{2.373}\right)</math>
Back substitution	Triangular matrix	<math>n</math> solutions	Back substitution^[30]	<math>O\mathord\left(n^2\right)</math>

In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.^[31]

Transforms

Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.

Operation	Input	Output	Algorithm	Complexity
Discrete Fourier transform	Finite data sequence of size <math>n</math>	Set of complex numbers	Schoolbook	<math>O(n^2)</math>
Discrete Fourier transform	Finite data sequence of size <math>n</math>	Set of complex numbers	Fast Fourier transform	<math>O(n \log n)</math>

Notes

Шаблон:Reflist

References

Шаблон:Reflist

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Computational complexity of mathematical operations

Содержание

Arithmetic functions

Algebraic functions

Special functions

Elementary functions

Non-elementary functions

Mathematical constants

Number theory

Matrix algebra

Transforms

Notes

References

Further reading

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты