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

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

در اینجا پیچیدگی، اشاره به پیچیدگی زمانی اجرای محاسبات در یک ماشین تورینگ مالتی تیپ است.A. Schönhage, A.F.W. Grotefeld, E. Vetter: Fast Algorithms—A Multitape Turing Machine Implementation, BI Wissenschafts-Verlag, Mannheim, 1994 نماد O بزرگ را برای توضیح نماد مورد استفاده ببینید.

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

 توابع حسابی 
عملوروذیخروجیالگوریتمپیچیدگیجمعدو عدد n رقمی N و Nیک عدد n+1 رقمیجمع کتاب درسی با انتقال رقمΘ(n), Θ(log(N))تفریقدو عدد n رقمی N و Nیک عدد n+1 رقمیجمع کتاب درسی با قرض گرفتنΘ(n), Θ(log(N))ضربTwoOne 2n-digit numberضرب طولانی کتاب درسیO(n2)Karatsuba algorithmO(n1.585)3-way Toom–Cook multiplicationO(n1.465)k-way Toom–Cook multiplicationO(nlog (2k − 1)/log k)Mixed-level Toom–Cook (Knuth 4.3.3-T)D. Knuth.O(n 2 log n)Schönhage–Strassen algorithmO(n log n log log n)Fürer's algorithmMartin Fürer.O(n log n 2O(log* n))تقسیمTwo n-digit numbersOne n-digit numberSchoolbook long divisionO(n2)Newton–Raphson divisionO(M(n))ریشه دومOne n-digit numberOne n-digit numberروش نیوتنNewton's methodO(M(n))Modular exponentiationTwo n-digit numbers and a k-bit exponentOne n-digit numberRepeated multiplication and reductionO(M(n) 2k)Exponentiation by squaringO(M(n) k)Exponentiation with Montgomery reductionO(M(n) k)

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

 توابع خاص 
بسیاری از روش‌های این بخش در Borwein و BorweinJ. Borwein & P. Borwein. موجودند.

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

 توابع غیرمقدماتی 
 ثابت‌های ریاضی 
این جدول پیچیدگی محاسباتی تقریب اعداد ثابت مشخصی را تا n رقم درست فراهم می‌کند.
ثابتالگوریتمپیچیدگیثابت طلایی، φNewton's methodO(M(n))ریشه دوم 2روش نیوتنO(M(n))عدد اویلر eBinary splitting of the Taylor series for the exponential functionO(M(n) log n)Newton inversion of the natural logarithmO(M(n) log n)Pi, πBinary splitting of the arctan series in Machin's formulaO(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 در nSchoolbook matrix multiplicationO(n3)Strassen algorithmO(n2.807)Coppersmith–Winograd algorithmO(n2.376)Optimized CW-like algorithmsO(n2.373)ضرب ماتریسییک ماتریس n در m و یک ماتریس m در pیک ماتریس n در pضرب ماتریسی کتاب درسیO(nmp)معکوس ماتریسیک ماتریس n در nیک ماتریس n در nروش حذفی گاوس-جردنO(n3)Strassen algorithmO(n2.807)Coppersmith–Winograd algorithmO(n2.376)Optimized CW-like algorithmsO(n2.373)دترمینانیک ماتریس n در nیک عددبسط لاپلاسO(n!)تجزیه LUO(n3)الگوریتم بارایس BareissO(n3)ضرب ماتریسی سریعO(n2.373)جایگذاری پسروماتریس مثلثیn جوابجایگذاری پسروJ. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.O(n2)

 منابع 

رده:الگوریتم‌های محاسباتی رایانه
رده:الگوریتم‌های نظریه اعداد
رده:فهرست‌های ریاضی
رده:مسئله‌های حل‌نشده در علوم رایانه
رده:نظریه پیچیدگی محاسباتی