수학 연산의 계산 복잡성

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "수학 연산의 계산 복잡성" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2015년 4월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

다음 표는 일반적인 수학 연산을 위한 다양한 알고리즘의 계산 복잡성을 나타낸다.

여기서 복잡성은 멀티테이프 튜링 기계에서 계산을 수행하는 시간의 복잡성을 가리킨다.^[1] 사용된 표기법에 대한 설명은 큰 O 표기법을 참조하십시오.

참고: 다양한 곱셈 알고리즘으로 인해 아래$$ $M{\displaystyle (n}$) ${\displaystyle M(n)}$은 선택한 곱셈 알고리즘의 복잡성을 나타낸다.

산술 함수

작전	입력	출력	알고리즘.	복잡성
덧셈	$두{\displaystyle }$ $개$의 n ${\displaystyle n}$ -자리$$ 숫자, $N{\displaystyle }$ ${\displaystyle$ N$}$ 및 N$$ ${\displaystyle N}$	$1n{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1}$- 자리$$ 번호	휴대품 포함 학교부록 추가	$\displaystyle \Theta(n),\테타(\log(N))}$
뺄셈	$두{\displaystyle }$ $개$의 n ${\displaystyle n}$ -자리$$ 숫자, $N{\displaystyle }$ ${\displaystyle$ N$}$ 및 N$$ ${\displaystyle N}$	$1n{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1}$- 자리$$ 번호	차입으로 교재 뺄셈	$\displaystyle \Theta(n),\테타(\log(N))}$
곱하기	두 $개$의 n ${\displaystyle n}$ -자리$$ 숫자	$1개$의 ${\displaystyle \mathrm{2n}}$ ${\displaystyle 2n}$ -자리$$ 번호	학교책 긴 곱하기	${\displaystyle O(n^{2})}$
			카라츠바 알고리즘	${\displaystyle O(n^{1.585)}$
			3방향 톰-쿡 곱하기	${\displaystyle O(n^{1.465})}$
			${\displaystyle k}$ ${\displaystyle k}$ -way$$ Toom-Cook 곱하기	${\displaystyle O(n^{\frac {\log(2k-1)}{\log k}}$
			혼합 레벨 톰-쿡(Knuth 4.3.3-T)[2]	${\displaystyle O(n\,2^{\sqrt {2\log n}\,\log n)}$
			쇤네게-스트라센 알고리즘	${\displaystyle O(n\log n\log \log n)}$
			총통의 알고리즘[3]	${\displaystyle O(n\log n\,2^{2\log ^{*}n}})$
			하비호벤 알고리즘[4][5]	${\displaystyle O(n\log n)}$
나누기	두 $개$의 n ${\displaystyle n}$ -자리$$ 숫자	$하나$의 n ${\displaystyle n}$ -자리$$ 숫자	교내 장분할	${\displaystyle O(n^{2})}$
			버니켈-지글러 분할-금융[6] 부문	${\displaystyle O(M(n)\log n)}$
			뉴턴-랩슨 사단	${\displaystyle O(M(n))}$
제곱근	$하나$의 n ${\displaystyle n}$ -자리$$ 숫자	$하나$의 n ${\displaystyle n}$ -자리$$ 숫자	뉴턴의 방법	${\displaystyle O(M(n))}$
모듈형 지수	두 $개$의 n ${\displaystyle n}$ -자리$$ 정수 및 $k{\displaystyle }$ ${\displaystyle k}$ -bit$$ 지수	$하나$의 n ${\displaystyle n}$ - 자리$$ 정수	반복 곱하기 및 감소	${\displaystyle O(M(n)\,2^{k}}}$
			제곱에 의한 지수화	$(\displaystyle O(M(n)\,k)}$
			몽고메리 축소를 통한 지수화	$(\displaystyle O(M(n)\,k)}$

대수 함수

작전	입력	출력	알고리즘.	복잡성
다항식 평가	$고정{\displaystyle }$ 크기 계수가 있는$$ 도 n ${\displaystyle n}$의 단일 다항식	한 개의 고정 크기 번호	직접평가	$\displaystyle \Theta (n)}$
			호너의 방법	$\displaystyle \Theta (n)}$
다항식 gcd($Z{\displaystyle \mathbb{}}$[ ${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle \mathb {Z}[x]]$ 또는$$ $F{\displaystyle }$[${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle F[x]}$ 초과$))$	고정 크기 정수 계수를 갖는$$ 도 $n{\displaystyle }$ ${\displaystyle n}$의 두 다항식	최대 $n{\displaystyle }$ ${\displaystyle n}$의 도 다항식 하나	유클리드 알고리즘	${\displaystyle O(n^{2})}$
			고속 유클리드 알고리즘(Lehmer)[7]	${\displaystyle O(M(n)\log n)}$

특수 기능

이 절의 많은 방법들은 Borwein & Borwein에서 주어진다.^[8]

기본 함수

기본 함수는 산술 연산, 지수 함수(${\displaystyle \exp }$ ${\displaystyle \exp }),$ 자연 로그(${\displaystyle \log }$ ${\displaystyle \log }),$ $$삼각 함수(${\displaystyle \sin }$, ${\displaystyle \cos }$ ${\displaysty \sin ,\cos })$ $$및 그 반대로 구성된다. 모든 기본 함수는 뉴턴의 방법에 의해 해석되고 따라서 반전될 수 있기 때문에, 기본 함수의 복잡성은 그 역 함수의 복잡성과 동등하다. 특히 복잡한 도메인에 있는$$ ${\displaystyle \exp }$ ${\displaystyle \exp }$ 또는$$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle \log }$ 중 하나를 복잡하게 계산할 수 있다면, 그 복잡성은 다른 모든 기본 기능에 대해 달성할 수 있다.

아래 n $크기{\displaystyle }$ n ${\displaystyle n}$은 함수를 평가할 정밀도의 자릿수를 가리킨다$$.

알고리즘.	적용가능성	복잡성
Taylor 시리즈; 반복된 인수 감소(예: ${\displaystyle \exp }$ ${\displaystyle }$( ${\displaystyle 2}$ x${\displaystyle }$)${\displaystyle }$=${\displaystyle }$[ ${\displaystyle \exp }$ ${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$$^{2$}}$$) 및 직접 합계	$\displaystyle \exp,\log,\sin,\cos,\arctan }$	${\displaystyle O(M(n)n^{1/2})$
테일러 시리즈; FFT 기반 가속	$\displaystyle \exp,\log,\sin,\cos,\arctan }$	${\displaystyle O(N)n^{1/3}(\log n)^{2}}$
Taylor 영상 시리즈, 이진 분할 + 비트 버스트 알고리즘[9]	$\displaystyle \exp,\log,\sin,\cos,\arctan }$	${\displaystyle O(N)(\log n)^{2}}$
산술-기하계 평균 반복[10]	$\displaystyle \exp,\log,\sin,\cos,\arctan }$	${\displaystyle O(M(n)\log n)}$

$O{\displaystyle }$( ${\displaystyle M}$( n${\displaystyle }$) ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(M(n)\log n)}$이(가) 기본 기능에 대한 최적의 복잡성인지는 알려져 있지 않다. 가장 잘 알려진 하한은 사소한 바인딩 Ω ${\displaystyle \Oomega$${\displaystyle \}(<img\; alt="\backslash Omega\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/24b0d5ca6f381068d756f6337c08e0af9d1eeb6f"\; style="vertical-align:\; -0.338ex;\; width:1.678ex;\; height:2.176ex;"\; papago-attr-id="166">M}$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle$ ($M(n$

비원소함수

함수	입력	알고리즘.	복잡성
감마함수	${\displaystyle n}$ ${\displaystyle n}$ -자리$$ 숫자	불완전한 감마 함수의 직렬 근사치	${\displaystyle O(N)n^{1/2}(\log n)^{2}$
	고정합리수	초기하계 열	${\displaystyle O(N)(\log n)^{2}}$
	${\displaystyle }$$m{\displaystyle }$${\displaystyle }$/ ${\displaystyle 24}$ ${\displaystyle m/24$$$$},$m ${\displaystyle m}$ 정수.	산술-기하계 평균 반복	${\displaystyle O(M(n)\log n)}$
초기하 함수 ${\displaystyle {}_{p}\!F_{q}}}$	${\displaystyle n}$ ${\displaystyle n}$ -자리$$ 숫자	(Borwein & Borwein에서 설명한 바와 같이)	${\displaystyle O(N)n^{1/2}(\log n)^{2}$
	고정합리수	초기하계 열	${\displaystyle O(N)(\log n)^{2}}$

수학적 상수

이 표는 주어진 상수에 대한 계산의 복잡성을 $n{\displaystyle }$ ${\displaystyle n}$ 정확한$$ 숫자에 제공한다.

상수	알고리즘.	복잡성
황금비율, $\varphi {\displaystyle }$ ${\displaystyle \phi }$	뉴턴의 방법	${\displaystyle O(M(n))}$
2, $2$의 제곱근 ${\$	뉴턴의 방법	${\displaystyle O(M(n))}$
오일러 번호, $e{\displaystyle }$ ${\displaystyle e}$	지수함수에 대한 Taylor 시리즈의 이진 분할	${\displaystyle O(M(n)\log n)}$
	뉴턴의 자연 로그 반전	${\displaystyle O(M(n)\log n)}$
Pi, $\pi {\displaystyle }$ ${\displaystyle \pi }$	마친 공식에서 아크탄 계열의 2진 분할	${\displaystyle O(N)(\log n)^{2}}$[11]
	가우스-레젠드르 알고리즘	${\displaystyle O(M(n)\log n)}$[11]
오일러의 상수, $\gamma {\displaystyle }$ ${\displaystyle \gamma }$	스위니의 방법(지수 적분 측면에서 근사치)	${\displaystyle O(N)(\log n)^{2}}$

수 이론

숫자 이론 계산을 위한 알고리즘은 계산 번호 이론에서 연구된다.

작전	입력	출력	알고리즘.	복잡성
최대공통점	두 $개$의 n ${\displaystyle n}$ - 자리$$ 정수	최대 $n개$의$${\$displaystyle n}$자리$$ 수를 가진 정수	유클리드 알고리즘	${\displaystyle O(n^{2})}$
			이진 GCD 알고리즘	${\displaystyle O(n^{2})}$
			좌우 k-ary 이진 GCD 알고리즘[12]	${\displaystyle O(n^{2}\log n)}$
			슈틸레-짐머만 알고리즘[13]	${\displaystyle O(M(n)\log n)}$
			쇤네게는 유클리드 강하 알고리즘을 제어[14]	${\displaystyle O(M(n)\log n)}$
자코비 기호	두 $개$의 n ${\displaystyle n}$ - 자리$$ 정수	${\displaystyle 0}$ ${\displaystyle 0$${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle -1}$ 또는$$ $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$	쇤네게는 유클리드 강하 알고리즘을[15] 제어	${\displaystyle O(M(n)\log n)}$
			슈틸레-짐머만 알고리즘[16]	${\displaystyle O(M(n)\log n)}$
요인	$m{\displaystyle }$ ${\displaystyle m}$보다 작은 양의 정수	1 $O{\displaystyle (m}$ ${\displaystyle \mathrm{로그}\mathrm{logm}}$) ${\displaystyle O(m\log$ m$)}$ - 자리$$ 정수	상향식 곱셈	${\displaystyle O(M(m^{2})\log m)}$
			이진 분할	${\displaystyle O(M(m\log m)\log m)}$
			$m{\displaystyle }$ ${\displaystyle m}$의 주요 요인 지수	${\displaystyle O}$(${\displaystyle M}$ ${\displaystyle \mathrm{로그}}$ log${\displaystyle }$m )${\displaystyle \mathrm{로그}}$ ${\displaystyle \log }$로그$$ m ) $displaystyle$ O($M(m\log m)\log \log$ m$)\},$[17] ${\displaystyle O(M(m\log m))}$[1]
원시성 검정	$n{\displaystyle }$ ${\displaystyle n}$ - 자리$$ 정수	참 또는 거짓	AKS 원시성 검정	${\displaystyle O({}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$) ${\displaystyle O(n^{6}}$ 또는$$[18][19] $O{\displaystyle ({}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$+ ${\displaystyle {\epsilon }^{}}$ ${\displaystyle O(n^{6+\varepsilon$ $\}\}\}),$[20][21] ${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$) ${\displaystyle O(n^{3}}),$ Agrawal의 추측을 가정한다$.$
			타원 곡선 원시성 증명	${\displaystyle O(n^{4+\varepsilon }})}$ 휴리스틱하게[22]
			바일리-PSW 원시성 검정	${\displaystyle O(n^{2+\varepsilon }})}$[23][24]
			밀러-라빈 원시성 검정	${\displaystyle O(kn^{2+\varepsilon }})}$[25]
			솔로바이-스트라센 원시성 검정	${\displaystyle O(kn^{2+\varepsilon }})}$[25]
정수 인자화	$A{\displaystyle }$ b ${\displaystyle b}$ -비트$$ 입력 정수	요인 집합	일반수 필드 체	${\displaystyle O(1+\varepsilon )^{b}}$[nb 1]
			쇼어 알고리즘	${\displaystyle }$O${\displaystyle }$( ${\displaystyle {b\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$) ${\displaystyle O(b^{3$ 양자 컴퓨터에

행렬 대수

다음의 복잡도 수치는 고정밀 부동 소수점 산술이나 유한장 연산의 경우와 마찬가지로 개별 원소가 있는 산술은 복잡도 O(1)를 갖는다고 가정한다.

작전	입력	출력	알고리즘.	복잡성
행렬 곱하기	두 $개$의 n ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times$ n$}$ 행렬$$	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬$$	학교책 매트릭스 곱하기	${\displaystyle O(n^{3})}$
			스트라센 알고리즘	${\displaystyle O(n^{2.807})}$
			코퍼스미스-위노그라드 알고리즘(은하 알고리즘)	${\displaystyle O(n^{2.376})}$
			최적화된 CW 유사 알고리즘[26][27][28][29](은하 알고리즘)	${\displaystyle O(n^{2.3728596})}$
행렬 곱하기	$1개$의 n${\displaystyle }$× ${\displaystyle m}${\$displaystyle n\time m}$ 행렬과$$ 1 $m{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle p}$ ${\displaystyle m\time p}$ 행렬$$	$1n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle p}$ ${\displaystyle n\time$ p$} 행렬$	학교책 매트릭스 곱하기	${\displaystyle O(nmp)}$
행렬 곱하기	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle \times }$ × ${\displaystyle n^{}}$ $\$ {\$displaystyle n\timees$ \$lceil n^{k$}\rceil$$ $}$ ${\displaystyle \mathrm{kn}}$ k ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle \lceil n^{k}\rceil$\rceil \$ceil n}$ 행렬$$ 1개(일부 k ${\displaystyle \ge }$ ${\displaystyle k\geq 0})$	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬$$	에 제공된 알고리즘	${\displaystyle O(}$ ${\displaystyle {}^{}}$ ${\displaystyle {\Omega (k}^{}}$)${\displaystyle {}^{}}$+ ${\displaystyle {ϵ}^{}}$) ${\displaystyle O(n^{\omega(k)+\epsilon$ $\}\}\},$ 여기서 $\Omega {\displaystyle (k}$) ${\displaystyle \omega(k)}$에 대한 상한이 주어진다$$.
행렬 반전*	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬$$	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬$$	가우스-요르단 제거	${\displaystyle O(n^{3})}$
			스트라센 알고리즘	${\displaystyle O(n^{2.807})}$
			코퍼스미스-위노그라드 알고리즘	${\displaystyle O(n^{2.376})}$
			최적화된 CW 유사 알고리즘	${\displaystyle O(n^{2.373})}$
단수 값 분해	1 $m{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle m\times n}$ 행렬$$	1 $m{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle m}$ ${\displaystyle m\time m}$ 행렬$$, 1 $m{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ $[\displaystyle m\properties n}$ 행렬$$ 하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\properties n}$ 행렬$$	비다이각화 및 QR 알고리즘	${\displaystyle O(mn^{2}+m^{2}n)}$ (${\displaystyle }$ ${\displaystyle \ge n}$ ${\displaystyle m\geq n}$)
		1 $m{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle m\time n}$ 행렬$$, 하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ $[\displaystyle n\property n}$ 행렬$$, & 하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\properties n}$ 행렬$$	비다이각화 및 QR 알고리즘	${\displaystyle O(mn^{2})}$ (${\displaystyle }$ ${\displaystyle \ge n}$ ${\displaystyle m\geq n}$)
결정인자	하나의 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬$$	한자리 숫자	라플라스 확장	$(\displaystyle O(n!)}$
			무분할 알고리즘[31]	${\displaystyle O(n^{4})}$
			LU 분해	${\displaystyle O(n^{3})}$
			바리스 알고리즘	${\displaystyle O(n^{3})}$
			빠른 행렬 곱하기[32]	${\displaystyle O(n^{2.373})}$
백 치환	삼각행렬	${\displaystyle n}$ $[\displaystyle n}$ 솔루션$$	백 치환[33]	${\displaystyle O(n^{2})}$

2005년에 헨리 콘, 로버트 클라인버그, 발라즈 스제게디, 크리스 우만스는 두 가지 다른 추측 중 하나가 행렬 곱셈의 지수가 2라는 것을 암시할 것이라는 것을 보여주었다.^[34]

변환

함수 변환 계산 알고리즘(특히 적분 변환)은 수학의 모든 영역, 특히 분석과 신호 처리에서 널리 사용된다.

작전	입력	출력	알고리즘.	복잡성
이산 푸리에 변환	$n{\displaystyle }$ 크기 n${\displaystyle$ n}의 유한 데이터 시퀀스	복잡한 숫자의 집합	고속 푸리에 변환	${\displaystyle O(n\log n)}$

메모들

참조

추가 읽기

• Brent, Richard P.; Zimmermann, Paul (2010). Modern Computer Arithmetic. Cambridge University Press. ISBN 978-0-521-19469-3.
• Knuth, Donald Ervin (1997). The Art of Computer Programming. Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. ISBN 978-0-201-89684-8.