پیچیدگی محاسباتی اعمال ریاضی
جدول زیر فهرست زمان اجرای الگوریتم‌های مختلف برای عملیات رایج ریاضی را نشان می‌دهد.
در اینجا پیچیدگی، اشاره به پیچیدگی زمانی اجرای محاسبات در یک ماشین تورینگ مالتی تیپ است. نماد 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(n) |
| Karatsuba algorithm | O(n) | |||
| 3-way Toom–Cook multiplication | O(n) | |||
| k-way Toom–Cook multiplication | O(n) | |||
| Mixed-level Toom–Cook (Knuth 4.3.3-T) | O(n 2 log n) | |||
| Schönhage–Strassen algorithm | O(n log n log log n) | |||
| Fürer's algorithm | O(n log n 2) | |||
| تقسیم | Two n-digit numbers | One n-digit number | Schoolbook long division | O(n) |
| 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) 2) |
| 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(n) |
| الگوریتم سریع اقلیدسی | 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)) |
| الگوریتم سلامین-برنت | O(M(n) log n) | |
| Euler's constant, γ | Sweeney's method (approximation in terms of the exponential integral) | O(M(n) (log n)) |
نظریه اعداد
الگوریتم‌های محاسبات نظریه اعداد در نظریه اعداد محاسباتی مطالعه می‌شوند.
جبر ماتریس
در جدول پیچیدگی محاسباتی زیر فرض می‌شود که حساب با عناصر انفرادی دارای پیچیدگی محاسباتی (1)O است.
| عمل | ورودی | خروجی | الگوریتم | پیچیدگی |
|---|---|---|---|---|
| ضرب ماتریسی | دو ماتریس n در n | یک ماتریس n در n | Schoolbook matrix multiplication | O(n) |
| Strassen algorithm | O(n) | |||
| Coppersmith–Winograd algorithm | O(n) | |||
| Optimized CW-like algorithms | O(n) | |||
| ضرب ماتریسی | یک ماتریس n در m و یک ماتریس m در p | یک ماتریس n در p | ضرب ماتریسی کتاب درسی | O(nmp) |
| معکوس ماتریس | یک ماتریس n در n | یک ماتریس n در n | روش حذفی گاوس-جردن | O(n) |
| Strassen algorithm | O(n) | |||
| Coppersmith–Winograd algorithm | O(n) | |||
| Optimized CW-like algorithms | O(n) | |||
| دترمینان | یک ماتریس n در n | یک عدد | بسط لاپلاس | O(n!) |
| تجزیه LU | O(n) | |||
| الگوریتم بارایس Bareiss | O(n) | |||
| ضرب ماتریسی سریع | O(n) | |||
| جایگذاری پسرو | ماتریس مثلثی | n جواب | جایگذاری پسرو | O(n) |
منابع
- ↑ A. Schönhage, A.F.W. Grotefeld, E. Vetter: Fast Algorithms—A Multitape Turing Machine Implementation, BI Wissenschafts-Verlag, Mannheim, 1994
- ↑ D. Knuth.
- ↑ Martin Fürer.
- ↑ http://planetmath.org/fasteuclideanalgorithm
- ↑ J. Borwein & P. Borwein.
- ↑ Davie, A.M.; Stothers, A.J. (2013), "Improved bound for complexity of matrix multiplication", Proceedings of the Royal Society of Edinburgh, 143A: 351–370, doi:10.1017/S0308210511001648
- ↑ Vassilevska Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF)
- ↑ Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014), arXiv:1401.7714
- ↑ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Addison-Wesley, Theorem 6.6, p. 241
- ↑ J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.