پیچیدگی محاسباتی اعمال ریاضی

جدول زیر فهرست زمان اجرای الگوریتم‌های مختلف برای عملیات رایج ریاضی را نشان می‌دهد.

در اینجا پیچیدگی، اشاره به پیچیدگی زمانی اجرای محاسبات در یک ماشین تورینگ مالتی تیپ است. نماد O بزرگ را برای توضیح نماد مورد استفاده ببینید.

توجه: با توجه به تنوع الگوریتم‌های ضرب، منظور از (M(n تعداد عملیات در الگوریتم انتخاب شده برای ضرب است.

توابع حسابی

عمل	وروذی	خروجی	الگوریتم	پیچیدگی
جمع	دو عدد n رقمی N و N	یک عدد n+1 رقمی	جمع کتاب درسی با انتقال رقم	Θ(n), Θ(log(N))
تفریق	دو عدد n رقمی N و N	یک عدد n+1 رقمی	جمع کتاب درسی با قرض گرفتن	Θ(n), Θ(log(N))
ضرب	Two	One 2n-digit number	ضرب طولانی کتاب درسی	O(n2)
			Karatsuba algorithm	O(n1.585)
			3-way Toom–Cook multiplication	O(n1.465)
			k-way Toom–Cook multiplication	O(nlog (2k − 1)/log k)
			Mixed-level Toom–Cook (Knuth 4.3.3-T)	O(n 2√2 log n log n)
			Schönhage–Strassen algorithm	O(n log n log log n)
			Fürer's algorithm	O(n log n 2O(log* n))
تقسیم	Two n-digit numbers	One n-digit number	Schoolbook long division	O(n2)
			Newton–Raphson division	O(M(n))
ریشه دوم	One n-digit number	One n-digit number	روش نیوتنNewton's method	O(M(n))
Modular exponentiation	Two n-digit numbers and a k-bit exponent	One n-digit number	Repeated multiplication and reduction	O(M(n) 2k)
			Exponentiation by squaring	O(M(n) k)
			Exponentiation with Montgomery reduction	O(M(n) k)

توابع جبری

عملیات	ورودی	خروجی	الگوریتم	پیچیدگی
محاسبه چندجمله‌ای	یک چند جملهای از درجه n که ضرایب چندجمله‌ای با اندازه ثابت هستند	یک عدد با اندازه ثابت	محاسبه مستقیم	Θ(n)
			روش هورنر	Θ(n)
بزرگ‌ترین مقسوم علیه مشترک gcd (روی Z[x] یا F[x])	دو چندجمله‌ای از درجه n که ضرایب با اندازه ثابت دارند	یک چند جمله‌ای از درجه حداکثر n	الگوریتم اقلیدسی	O(n2)
			الگوریتم سریع اقلیدسی	O(M(n) log n)

توابع خاص

بسیاری از روش‌های این بخش در Borwein و Borwein موجودند.

توابع مقدماتی

توابع مقدماتی با ترکیب عملیات حسابی، تابع نمایی (exp)، لگاریتم طبیعی (log)، توابع مثلثاتی (sin، cos) و معکوس آنها ساخته می‌شوند. پیچیدگی یک تابع مقدماتی معادل با پیچیدگی معکوس آن است زیرا همه توابع مقدماتی تحلیلی هستند و بنابراین با روش نیوتن معکوس پذیرند. به ویژه اگر هر کدام از exp یا log در حوزه اعداد مختلط را بتوان با یک پیچیدگی حساب کرد آنگاه آن پیچیدگی برای همه توابع مقدماتی دیگر دست یافتنی است.

ثابت‌های ریاضی

این جدول پیچیدگی محاسباتی تقریب اعداد ثابت مشخصی را تا n رقم درست فراهم می‌کند.

ثابت	الگوریتم	پیچیدگی
ثابت طلایی، φ	Newton's method	O(M(n))
ریشه دوم 2	روش نیوتن	O(M(n))
عدد اویلر e	Binary splitting of the Taylor series for the exponential function	O(M(n) log n)
	Newton inversion of the natural logarithm	O(M(n) log n)
Pi, π	Binary splitting of the arctan series in Machin's formula	O(M(n) (log n)2)
	الگوریتم سلامین-برنت	O(M(n) log n)
Euler's constant, γ	Sweeney's method (approximation in terms of the exponential integral)	O(M(n) (log n)2)

نظریه اعداد

الگوریتم‌های محاسبات نظریه اعداد در نظریه اعداد محاسباتی مطالعه می‌شوند.

جبر ماتریس

در جدول پیچیدگی محاسباتی زیر فرض می‌شود که حساب با عناصر انفرادی دارای پیچیدگی محاسباتی (1)O است.

عمل	ورودی	خروجی	الگوریتم	پیچیدگی
ضرب ماتریسی	دو ماتریس n در n	یک ماتریس n در n	Schoolbook matrix multiplication	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)
			Optimized CW-like algorithms	O(n2.373)
ضرب ماتریسی	یک ماتریس n در m و یک ماتریس m در p	یک ماتریس n در p	ضرب ماتریسی کتاب درسی	O(nmp)
معکوس ماتریس	یک ماتریس n در n	یک ماتریس n در n	روش حذفی گاوس-جردن	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)
			Optimized CW-like algorithms	O(n2.373)
دترمینان	یک ماتریس n در n	یک عدد	بسط لاپلاس	O(n!)
			تجزیه LU	O(n3)
			الگوریتم بارایس Bareiss	O(n3)
			ضرب ماتریسی سریع	O(n2.373)
جایگذاری پسرو	ماتریس مثلثی	n جواب	جایگذاری پسرو	O(n2)