پیچیدگی محاسباتی مجانبی
(تغییرمسیر از پیچیدگی رایانشی ناهمساویک)
 | این نوشتار یا بخش، مفهوم کامل و روشن را نمیرساند. لطفاً با ویرایش کردن یا افزودن جزئیات بیشتر به بهبود مقاله کمک کنید و سپس این برچسب را بردارید. |
مطابق با نظریه پیچیدگی محاسباتی، از تحلیل مجانبی برای تخمین پیچیدگی محاسباتی الگوریتم‌ها و مسائل محاسباتی، با استفاده از نماد O بزرگ استفاده می‌شود که به آن پیچیدگی محاسباتی مجانبی (به انگلیسی: Asymptotic computational complexity) می‌گویند.
بازه
[ویرایش]با توجه به منبع رایانشی، پیچیدگی زمان ناهمساو و پیچیدگی فضای مجانبی تخمین زده می‌شوند. دیگر رفتارهای مجانبی که تخمین زده می‌شوند عبارتند از پیچیدگی مداری (به انگلیسی: circuit complexity) و اندازه‌گیری‌های متنوع پردازش موازی مانند تعداد پردازنده‌ها (ی موازی) است.
از انتشار مقاله یوریس هارتمانیس و ریچارد استیرنز[۱] در ۱۹۶۵ و همچنین مقاله مایکل گری و دیوید اس جانسون در ۱۹۷۹ دربارهٔ ان‌پی کامل،[۲] اصطلاح تحلیل الگوریتم‌ها، معمولاً به پیچیدگی رایانشی ناهمساویک گفته می‌شود.
منابع
[ویرایش]- ↑ Hartmanis, J.; Stearns, R. E. (1965). "On the computational complexity of algorithms". Transactions of the American Mathematical Society. 117: 285–306. doi:10.1090/S0002-9947-1965-0170805-7.
- ↑ Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co. , 1979.