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

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

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

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

توابع حسابی

توابع جبری

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

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

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

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

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

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

منابع 

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